5
$\begingroup$

I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so that it could be evaluated (by adding an evaluate method if need be in the class some time later)

The simplest solution I came up with was to store this expression in a stack (push(a), push(+), push(b)....), or may be even in an array (arr[0] = a, arr[1] = +...)

I feel like this is bad design and I read online that a binary tree (expression tree) is better to represent such an expression, but I am not sure why it is better.

Can someone help me understand this? Does the binary expression tree provide some benefits over storing in a stack?

$\endgroup$
4
$\begingroup$

Different representations are useful for different purposes. Think what kinds of things you might want to do with the expression, and think how each of them would be done using the stack representation and using the binary tree representation, and choose for yourself.

For fun, you may also want to consider something completely different, e.g. the english language representation: e.g. "the product of the sum of a and b, and the difference between c and d over e", or the representation as X86 machine code which would compute this expression, etc.

Things you may want to do with an expression (in any particular program you would probably need only a small subset of these):

  • Evaluate it, given certain values of the variables
    • Just once
    • Evaluate the same expression repeatedly for different values, with very high performance requirements
  • Perform simple algebraic manipulation, e.g. simplifications such as replacing x - x => 0, x*1 => x, etc.
  • Perform sophisticated algebraic manipulation on it, e.g. factorize the polynomials, compute derivatives or integrals.
  • Understand the expression stored in a variable when you're debugging the program
  • Format it as a string for displaying to the user
  • Render it as a mathematical expression to MathML
  • Draw it as a mathematical expression on a Javascript canvas
  • Compare two expressions for equivalence
  • Compare two expressions for equivalence ignoring variable names, e.g. a * a + b being equivalent to p * p + q
  • Convert a user-supplied string into an expression, checking it for well-formedness
  • ...

Honestly speaking, I can find only one item of these for which the stack representation can possibly make things easier than the binary tree representation, and the array representation seems just completely useless.

$\endgroup$
  • $\begingroup$ Thanks, that makes sense. If I'm not wrong, the one item that you said is easier with stack implementation is the first bullet point? $\endgroup$ – Shobit Feb 15 '15 at 9:58
  • $\begingroup$ The second part of the first point :) (more precisely, it is easier to generate machine code from the stack representation). $\endgroup$ – jkff Feb 15 '15 at 17:09
0
$\begingroup$

In general, syntax is represented via an abstract syntax tree. This tree structure captures the hierarchy, precedence, and logical structure of its input, but not its formatting. The AST will not necessarily be a binary tree, although nodes denoting binary operators will have two child nodes.

In pseudocode, AST classes could look like this:

interface Ast {
}

class Literal(@value: Float) implements Ast {
  def value = @value
}

class Variable(@name: String) implements Ast {
  def name = @name
}

abstract class Binop(@left: Ast, @right: Ast) implements Ast {
  def left = @left
  def right = @right
}

class Add extends Binop { }
class Subtract extends Binop { }
class Multiply extends Binop { }
class Divide extends Binop { }

interface AstVisitor[A] {
  def visit(ast: Literal): A
  def visit(ast: Variable): A
  def visit(ast: Add): A
  def visit(ast: Subtract): A
  def visit(ast: Multiply): A
  def visit(ast: Divide): A
}

Your expression (a + b) * ( c - d / e) could then be represented as

Multiply(Add(Variable("a"), Variable("b"),
         Subtract(Variable("c"),
                  Divide(Variable("d"), Variable("e"))))

Different visitors could then implement different functionality. For example, an evaluator would look like this:

class Evaluator(@env: Map[String, Float]) implements AstVisitor[Float] {
  def visit(ast: Literal) =
    ast.value
  def visit(ast: Variable) =
    env.get(ast.name)
  def visit(ast: Add) =
    this.visit(ast.left) + this.visit(ast.right)
  def visit(ast: Subtract) =
    this.visit(ast.left) - this.visit(ast.right)
  def visit(ast: Multiply) =
    this.visit(ast.left) * this.visit(ast.right)
  def visit(ast: Divide) =
    this.visit(ast.left) / this.visit(ast.right)
}

Other visitor classes could assume responsibilities such as rendering the expression in normal mathematical notation, or performing transformations such as constant folding or other optimizations.

Due to its versatility, using an AST is common in compiler construction, but in simple cases it's going to be absolute overkill. If you only want to evaluate simple arithmetic expressions, a stack is vastly simpler.

Let's assume that the tokens on our stack or list can be of type Float, String (for variables), Lparen, Rparen, Plus, Minus, Mul, and Div. Then your expression would be represented as

(Lparen, "a", Plus, "b", Rparen, Mul, Lparen, "c", Minus, "d", Div, "e", Rparen)

Evaluating this stack ends up being the same problem as parsing it into an AST. For arithmetic expressions, we can use the Shunting-yard algorithm to translate it into Reverse Polish notation, which reorders the elements as

(Mul, Plus, "a", "b", Minus, "c", Div, "d", "e")

Note that this is essentially our AST structure flattened into a list, and that all parens have been made unnecessary. Instead of reassembling the expression in Polish notation, the Shunting-yard algorithm can be trivially modified to either assemble an AST or to directly evaluate the expression. Where the SYA pops an operator from the temp stack and adds it to the result stack, a direct evaluator would pop the operator from the temp stack, the arguments from the result stack, perform the operation, and push the result onto the result stack. Assembling an AST has the difference that instead of calculating a result, we create an AST object and push it onto the result stack.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.