Как оценить любое заданное выражение

Question

Как вы, учитывая любое строковое выражение, заселяете дерево?

У меня есть задание, на которое я застрял.

Мне нужно оценить следующее выражение ((5 * 10) /2 - ((2 + 3) + 6)) с использованием любой структуры данных.

Используя стек, я могу проверить, что строка хорошо сформирована. Но как я могу добавить различные значения в дерево и затем оценить их по порядку.

Пожалуйста, дайте мне какие-то намеки, вы можете иметь о том, как я могу читать строку (((490 * 9)/2)/5/6 - ((2/4 + 3) + 6 * 5))

Например, как я могу получить (-) является корнем из трех, когда это пятнадцатый подстроки в входное выражение? Как я могу убедиться, что выражение (/) 6 происходит после того, как (/) 5 и т.д.

Answer 1

Что вы ищете представлена ​​здесь: http://www.codeproject.com/Articles/88435/Simple-Guide-to-Mathematical-Expression-Parsing

Answer 2

Скобки обозначают порядок операций так же, как, как вам использовали стек, чтобы убедиться, что все согласовано, вы можете разобрать эти совпадения и использовать их в качестве элементов в дереве, чтобы создать иерархию для оценки, где операторы являются дочерними элементами каждого по ширине круглых скобок.

Answer 3

Отредактируйте второй: оп уточнить, см другие ответы

Answer 4

Другие ответы здесь охватывают чтение дерева выражения в памяти, но они не охватывают оценки дерева, как только вы построили.

Общая стратегия оценки дерева заключается в том, что дерево должно состоять из узлов и листьев, где узлы являются операторами с дочерними элементами, а листья являются постоянными значениями. Например, выражение (((490 * 9)/2)/5/6 - ((2/4 + 3) + 6 * 5)) преобразует в дерево

 
         - 
       / \ 
       /  \ 
       div   + 
      / \  / \ 
      div  6  +  * 
     / \  /\ /\ 
     div  5  div 3 6 5 
    / \  / \ 
    *  2  2  4 
/ \ 
450 9 

Чтобы оценить это дерево, вы начинаете с корня. Сначала вы рекурсивно оцениваете левое поддерево и правое поддерево, а затем применяете оператор к результатам двух оценок поддерева. Каждый лист (число) оценивает себя.

В этом случае, вы должны начать с корня (-), оценить левое поддерево вниз до 73,5, оценить правое поддерево до 33,5, и вычитать, чтобы получить окончательный результат 40.

в качестве более точный пример, давайте посмотрим на узлы в левом углу дерева, после того, как было сделано несколько уровней рекурсивных вызовов. Лист 450 оценивается до 450, лист 9 оценивается до 9, а узел (* 450 9) (записывающий узлы дерева в нотации в стиле Lisp) оценивается до 4050. Таким образом, из узла (/ (* 450 9) 2) левый рекурсивный вызов оценивается до 4050 и правый рекурсивный вызов оценивается равным 2, а это означает, что общий узел оценивается до 2025. Пока вы делаете рекурсивные вызовы из узлов перед объединением значений и убедитесь, что каждый лист оценивает себя, оценка дерева проста.

Answer 5

оценить любую строку [представляющую математическое] выражение

Вам нужно сделать три вещи:

• определяет тип для абстрактного синтаксического дерева, представляющими на вашем языке
• Написать рекурсивный анализатор спуска для вашего синтаксиса
• написать интерпретатор для вашего синтаксиса

Вы можете сделать это очень легко.

Я буду использовать обозначение Haskell, так как оно кратким, но вы можете перевести его, если хотите.

Тип для вашего языка:

data Exp = Op BinOp Exp Exp 
     | Lit Int 

data BinOp = Plus 
      | Times 
      | Div 
      | Sub 

теперь мы можем написать интерпретатор для выражений в этом языке:

eval :: Exp -> Int 
eval (Lit n)  = n 
eval (Op o e1 e2) = 
    let v1 = eval e1 
     v2 = eval e2 
    in case o of 
     Plus -> v1 + v2 
     Times -> v1 * v2 
     Sub -> v1 - v2 
     Div -> v1/v2 -- note, may fail! 

Ok. Итак, это оценщик терминов на вашем языке. Теперь напишите рекурсивный парсер спуска ...