Expression Parser
This applet with an exercise to make a binary tree that parsed simple mathematical expressions, such as 3+4*5.
Enter the expression in the text field. The Evaluate button will evaluate the current expression and show the result.
The parser is very simple. Addition, subtraction, multiplication and division are allowed, but no parentheses. The parser understands that multiplication and division have a higher precedence. Error handling is minimal. Invalid tokens should be ignored, but there's a possibility that illegal expressions will cause the applet to break.
Parsing is done left to right, taking precedence into account. In this version, I've adjusted the applet to do a more balanced parsing, to improve the presentation of the tree.
Design Notes
Parsing Strings
The StringParser class is a simple Builder pattern that converts a string into a tree of ParseTokens. StringParser is called every time the controller determines that its text field has changed. This means that for each keystroke the applet creates a new expression parse tree.
The Parse Tree
The parse tree containts two types of nodes: numbers, which are leaf nodes, and operators, which are container nodes. In this case, I've implemented the Composite pattern; the abstract class ParseToken allows users to treat all nodes identically.
The main method of the parse tree is evaluate() -- to return the value expressed by the tree. evaluate() is implemented recursively for operator nodes; an operator returns the value of its operation applied to the value of its left and right children.
Operator nodes contain an OpAction class which implements the particular operator.
The View
The view is a TreePane, a modified JPanel that knows where to put nodes in a binary tree. Each time the controller tells the TreePane to update, it gets the current model and walks the ParseToken tree, creating GraphNodes to handle the drawing.