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.
