The main focus for this project was to implement an equation parser, and the UI was initially only added for me to test the parser, but slowly it grew into the calculator with graphing functionality shown here.
The Equation Parser
My requirements for the parser were to allow for the expression to be entered as it would be typed if written by hand (on a single line) and obviously maintain correct order of operation and allow for constants and implicit multiplication.
Implicit multiplication means that the multiplication sign is not required between terms, number*term, number*constant. E.g. if an expression is written as (2+3)(2+3), this will be parsed as (2+3)*(2+3). Same for 2xy, this is parsed as 2*x*y.
The order of operation is parentheses first, starting from the inner most, then exponents (power), then multiplication and division and then addition and subtraction. For mul/div and add/sub, the operation is performed left to right.
By implementing this order, the expression entered as 2*5^2 will be parsed as 2*(5^2) = 50, whereas if parsed left to right the result would have been 2*5^2 = 100 (2*5 = 10, then 10^2 = 100, incorrect).
One minor issue in the current implementation is that the implicit multiplication does not have higher order than a ‘regular’ multiplication, this means that an expression 1/2x will be parsed as 1/2*x instead of 1/(2*x). E.g. if x is 5, then the result is 1/2*5 = 2.5, not 1/(2*5) = 0.1 as one might expect.
Parser Implementation
The parser implementation is EquationParser.cs located in CommonUtils.
To achieve the order of parentheses, the parsing is implemented as a recursive parsing in Term where each set of parentheses creates a new term. The Term contains a stack of EquationElements, and during the first pass elements are added to the stack as they are parsed. When a parentheses is found, the matching end parentheses is found and a new term is created based on this substring, and this new term is then added to the current terms stack.
E.g. 2*(3+5) will result in a stack as shown below:
If a parsed element is of type EquationValue and the previous element on the stack is of the same type, then an implicit multiplication is assumed and a * Operator is added to the stack.
Another check done when a value is added to the stack is to check for sign operator. If a value is added and the previous 2 elements on the stack are operator elements and the previous is a – operator, then this operator is removed from the stack and the sign flag is set on the value instead.
Any calculation within a term is performed left to right (top to bottom), so the next step is to create new terms based on the order of operations.
First, a pass is done where new terms are created for the exponent ^ operator. If the given operator is found, then a new term is created and the left value, operator and right value are added to the term. Then if the next operator is of same type, this operator plus the following value is added to same term.
Second pass is to combine * / into terms.
This is the code in Term.Parse:
public void Parse(string equation, EquationElement root)
{
Stack.Clear();
Parse(equation, 0, root);
CombineTerms(new char[] {'^'});
CombineTerms(new char[] {'*', '/'});
}
During parsing, each type of element is being asked if the current position in the equation is known to the type. The order in which they are asked is:
- Operator
- Number
- Constant
- Function
- Variable
- Term
- Throw exception
During the parsing, if any error is encountered, an exception is thrown.
- The Operator looks for */+-^
- The Number looks for any ‘0’..’9’ characters.
- The Constant looks for ‘pi’ and ‘e’
- The Function looks for some predefined
static functions
- The
Variable class (called Constant in the UI) does a lookup in the root element for a matching name.
The resulting value is returned in Term.Value. This call iterates the stack and performs the calculation per element in the stack.
Unit Test
To make sure I didn’t break any functionality during implementation, I created a small set ot tests that are performed on startup. These are located in EquationUnitTest and each were added as a new functionality was added.
Limitations
One limitation in the parser is the precision of the double. It is possible to enter a simple expression which should result in an integer value but instead shows a value off by 1 on the 15th decimal. I did try to change the parser to use decimal instead as it has much higher precision, but the range for this type is too limited so I chose to stay with double.
Another limitation is the missing support from complex numbers, and currently I do not plan to add support for this.
The Calculator UI
As mentioned in the beginning, the main focus for this project was the equation parser and not really the UI so I will not go into detail of how this is implemented since it is all pretty basic WPF.
I have added the following functionality to the calculator page.
Shortcut selection of Stack (Alt-1), Input (Alt-2) and Constant field (Alt-3). This could probably have been defined in XAML, but I coded it instead.
Perform calculation on Enter. If focus is on the input field, the field is cleared. If focus is on the constant field, the calculation is performed, but field is not cleared. This allows for quick test of multiple constant values for the same equation.
History is kept for both input and constant field, history can be accessed using arrow up/down or the dropdown.
If the first letter entered is an operator ‘ans’ is inserted to continue calculating using the previous answer. For instance 3+4 <Enter> + 1 <Enter> = 8. ‘Ans’ can be used anywhere in the expression. This will insert the last calculated value.
I did not add any keypad as I personally find it easier to use the keyboard to enter values into the textbox rather than use the mouse to click some buttons to enter the same values.
I really like the dark style used in Kaxaml so I tried to create a similar looking style. The style is defined by hand so I did not do anything fancy with animation when redefining the button style.
The Graph
The graph control is defined in CommonUtils.GraphicalCanvas and is called CanvasCtrl. This is still a work in progress, but currently it supports multiple layers, zoom (mouse wheel) and pan (mouse wheel pressed).
For now, the functionality of the graph is pretty limited. The grid is fixed 20x20 with the implementation defined in the CanvasLayer derived class called GraphGrid. Center will center the grid and Zoom will set the zoom level so 10 units will be visible in one direction.
One layer is added to the graph for each equation in the list. This EquationLayer recalculates its graph in the OnRender method. This method is called by the graph control whenever the graph is resized of panned.
The question when graphing an equation is how many samples to calculate. Not enough samples and you do not get an accurate picture of the graph, and too many samples will make the graph very sluggish when updating.
After a few tries, I ended up using the pixel width of the graph as my number of samples. This works well for any graph with a smooth change, but the next problem I ran into was when trying to graph a function like shown below -0.1/(x-1), this function goes close to positive infinity before becoming undefined (x = 1) and the wraps to close to negative infinity.
The 2 problems I had were:
- A line would be drawn from the max to min value, which in the graph appears as a vertical line.
- When zooming out, the line would disappear because of the low number of samples.
To solve #1, I added a check for when the y value changes between positive and negative (or vice versa), and when a change is detected, I look at the slop of the previous sample and the current sample, and if the slope changed too then a NaN value is inserted, and this NaN is used to break the graph while adding LineSegments to the PathFigure. This is done in OnRender.
For #2, I decided to simply split the one sample interval into 10 samples and find the min and max value and add those values to the sample list. This works well when the graph is zoomed in, but as soon as you zoom out the sample interval is too low and the graph gets distorted. E.g. a graph of tan(x) can show some really interesting patterns when zoomed as shown below where each spike should go to infinity.
What's Next
I have a few features I want to add to the graph, one is zoom of selection and the other is y-value tracking of the current selected graph when moving the mouse. I will update the project once this is available.
Revision
- 11/09/2010
- Uploaded fix for
double.Parse. Now both . and , are accepted for decimal seperator.
- 11/17/2010
- Added missing functions and fixed the nested function as suggested by Arjen.
- A function now supports multiple nesting of functions, e.g., "
cos(2min(pi(1/2), 3.14/2))"
- Added support for equation as variable value, like
m_term.SetVar("x", "2pi");
- This sets the variable
x to 2*pi.
Atan2 function removed for now as it is not properly parsed
- 11/25/2010
- Fixed the order of operation for the power operator. If a term is raised to a power which is raised to a power, then the calculation should be performed top down (right to left). I added
CombineTopDown as an extra pass after CombineTerms('^') is called.
Now 2^2^3 gives the correct answer 256.
At the same time, the signed flag is moved from the left term to the new term, so now -1^2 gives the correct answer -1 and not 1.
The following tests have been added to the unit test.
Assert("2^2^3", Math.Pow(2, Math.Pow(2,3)));
Assert("(2^2)^3", Math.Pow(Math.Pow(2, 2),3));
Assert("-(-1)^2", -1);
Assert("-1^2", -1);
Assert("(-1)^2", 1);
m_term.SetVar("x", 0);
Assert("-(x-1)^2+4", 3);
Support for variables with numbers, e.g. x2 supported using the fix provided by Arjen. Atan2 is not yet available (forgot to uncomment line 736 in EquationElements).
