Mathematical Expression Evaluation

excerpt: Trees can be used to model mathematical expressions by creating an inter node for each operator and a leaf node for each numeric value.

Trees can be used to model mathematical expressions by creating an inter node for each operator and a leaf node for each numeric value. Mathematical expressions can be broken down into subexpressions that must be evaluated before the entire expression is evaluated. For example, the expression (7 x 12) / (8 + 5) can be broken down into the subexpressions 7 x 12 and 8 + 5, these two subexpressions must be evaluated first. The results of these two calculations must be divided to get the final result.

The tree consisting of the expression can be modeled by building subtrees to represent the subexpression. The subtrees are joined with the root that represents the operation that combines the subexpressions - in this case, division. The diagram shows the tree representing the expression (7 x 12) / (8 + 5).

Each internal node has children representing its operands. For example, the operators such as + and / have left and right children that the operator must combine. The leaf nodes can be thought of as special opertors that convert a text value into a numeric value. So the leaf nodes must hold their text.

The node class must have a method to evaluate the node. The method should examine the type of node and then return an appropriate result. For example, if the operator is -, the method should recursively make its operands evaluate their subexpressions and then it can add the results.

Dijkstra’s two-Stack Algorithm for Expression Evaluation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

def evaluate(expression)
  input = expression.chars
  
  operators = []
  values = []
  
  for c in input
    if c == '('
    elsif c == '+'
      operators.push(c)
    elsif c == '-'
      operators.push(c)
    elsif c == '*'
      operators.push(c)
    elsif c == '/'
      operators.push(c)
    elsif c == 'sqrt'
      operators.push(c)
    elsif c == ')'
      operator = operators.pop
      value = values.pop
      
      if operator == '+'
        value = values.pop + value
      elsif operator == '-'
        value = values.pop - value
      elsif operator == '*'
        value = values.pop * value
      elsif operator == '/'
        value = values.pop / value
      elsif operator == 'sqrt'
        value = Math.sqrt(value)
      end
      values.push(value)
    else
      values.push(c.to_i)
    end
  end
  
  values.pop
end

p evaluate('(1*2)')