Expression Parser and Evaluator

Enter an expression.
Click Parse to parse and print the post-order traversal of the parse tree.
Click Evaluate to evaluate expression consisting of single digits and operations.
Click Back to go back to the previous page.
Download source of Parser.java.

Discussion of Recursive Descent Parser for arithmetic expressions using +, -, *, / and 0-9 digits. The following rules are parsed:

     expression ::= term | expression addop term
     addop ::= + | -
     term ::= factor | term mulop factor
     mulop ::= * | /
     factor ::= digit | ( expression )
     digit ::= 0..9

The parsing generates a parse tree of the expression that may be used to unambiguously evaluate the expression. The parse tree of the expression
3+5*7-4 yields:

                                          expr
                -                         / - \      
As symbols     / \                     expr   term
              +   4                    / + \     \
             / \                   expr   term  factor     As rules followed:
            3   *                    /    / * \     \ 
               / \                term  term factor digit
              5   7                /    /       \      \
                              factor  factor   digit    4
                                 /     /          \
                              digit  digit         7 
                               /      /
                              3      5

By traversing the tree left-to-right and printing post-order the terms of the expression tree as visited produces:

3 5 7 * 4 - +

which is the post-order representation for the above parse tree. The post-order representation can be evaluated without regard to
operator precedence.

Document last modified: