Introduction
Modern calculators solve differential equations and draw plots. They work with trigonometry, hyperbolic, logarithmic, statistic and other functions. Modern calculators contain processors that are much stronger than their predecessors in old "Apollo"like spaceships. This article describes the easiest way to build a parser with the ability to analyze complex mathematical expressions and evaluate them. The algorithm is the one that is commonly used in the calculators.
Problem Definition
Let's decide what kind of expressions our calculator should handle.
Simple operations: 
(2+3)*4/5^5 
Unary operators: 
6 
Single functions: 
2^3*cos(pi) 
Functions with more than one parameter: 
Log(10,100) 
Rightside operators: 
x! 
Variables assignment 
x=y=10; 
Reverse Polish Notation and Shunting Yard Algorithm
A Prefix (Polish) notation was introduced in 1920 by the Polish mathematician Jan Lukasiewicz. It is a mathematical notation wherein every operator follows all of its operands. It is also known as Postfix notation. Reverse Polish notation (RPN) was invented by Australian philosopher and computer scientist Charles Hamblin in the mid1950s, to enable zeroaddress memory stores. Hamblin presented his work at a conference in June 1957, and published it in 1957 and 1962.
In Reverse Polish notation, the operators follow their operands. Infix a + b changes to ab+; (a + b)*c changes to ab+c*. One of the RPN advantages is that it obviates the need for parentheses. The main advantage is that it's easy to use RPN with stack (firstinlastout) structures.
The shunting yard algorithm is a method for parsing mathematical equations specified in infix notation. It can be used to produce output in RPN. The algorithm was invented by Edsger Dijkstra and named the "shunting yard" because its operation resembles that of a railroad shunting yard. Like the evaluation of RPN, the shunting yard algorithm is stackbased. One of the stacks contains operands (digits and variables). Another stack contains all operators (+, , *, /, etc. and functions that are treated as operators).
Inside the Shunting Yard Algorithm
This is a brief example of how "shunting yard" works. Input expression: (2+3)*4/5;
First of all, we have to push a special "sentinel" operator into the operators stack. The sentinel is used to separate operations inside the parentheses and to indicate the bottom of the stack.
The parser reads the expression from left to right. The first token is "("  right parenthesis. The sentinel is pushed into the operators stack. When the parser finishes processing the current token (speaking about any token), it reads the next token, stores it into the "token" variable and processes it.
 Current token: "2"  an operand. Push it into the operands stack. Read the next token.
 Current token: "+"  an operator. Push it into the operators stack. Read the next token.
 Current token: "3"  an operand. Push it into the operands stack. Read the next token.
 Current token: ")"  right parenthesis. Evaluate both stacks until the sentinel is reached.
Operands 
Operators 
3 
+ 
2 
#, parenthesis 

#, bottom of the stack 
Calculation: Pop "+" from the stack. Compare the operator's precedence. "#" has lower precedence than "+". That's why "+" is processed. "+" is a binary operator; pop two operands ("3" and "2") from the Operands stack. Calculate 2+3 and push the result into the stack. The sentinel (#) is reached. Pop the sentinel from the stack and read the next token.
 Current token: "*"  an operator. Push it into the operators stack. Read the next token.
 Current token: "4"  an operand. Push it into the operands stack. Read the next token.
 Current token: "/"  an operator. Compare operators' precedence. "*" has the same precedence as "/". When the token operator's precedence is lower than the stack operator's precedence, the operator in the stack is processed before the current operator.
Calculation: Pop "*" from the stack. Compare the operators' precedence. "#" has lower precedence than "*". "*" is a binary operator; pop "5" and "4" from the operands stack. Calculate 5*4 and push the result back into the stack. Push "/" into the stack. Read the next token: (2+3)*4/5.
 Current token: "5"  an operand. Push it into the operands stack. Read the next token.
 The last token is ";"  END indicator. We can process both stacks until the sentinel in the operators stack is reached.
Operands 
Operators 
5 
/ 
20 
# 
The result is 20/5 = 4
Let's take a look at any simple or complex mathematical expression. We know what kind of token should come first in infix notation. It's a unary operator (like unary minus), left parenthesis, a number or a variable. For instance: 10; a+b; (10x); The Primary()
function converts the current token to one of the described mathematical characters. The binary operator comes after a primary token. The Binary()
function evaluates binary operators. We'll also need some subroutine functions like:
NextToken()
 Reads the next token and stores it to the token
variable
Precedence()
 Returns the operator's precedence
ReadOperand()
 Parses the sequence of characters or digits to a number, a variable or a function
The beauty of the algorithm in its recursion. A listing below shows the basic algorithm's implementation in pseudoC#:
Stack Operands, Operators;
Token token;
Parse()
{
Operators.Push(Sentinel);
Binary();
Expect(End)
return Operands.Peek();
}
Binary()
{
Primary();
while token is a binary operator
{
PushOperator(token);
NextToken();
Primary();
}
while Operators.Peek != Sentinel
PopOperator();
}
Primary()
{
if token is operand
ReadOperand();
else if token is unary
PushOperator(ToUnary(token));
NextToken();
Primary();
else if token is left parenthesis
Operators.Push(Sentinel);
NextToken();
Binary();
Expect (Right parentesis);
Operators.Pop();
else
throw exception;
}
PushOperator(op)
{
while Operators.Peek() > op
PopOperator()
Operators.Push(op)
}
PopOperator()
{
if Operators.Peek is binary
o2 = Operands.Pop();
o1 = Operands.Pop();
op = Operators.Pop();
Operands.Push( Calculate(op, o1, o2) );
else
o1 = Operands.Pop();
op = Operators.Pop();
Operands.Push( Calculate(op, o1) );
}
private void Expect(expectedToken)
{
if (token == expectedToken)
{
NextToken();
return;
}
else
throw exception
}
As you can see, the basic implementation is very easy. This scheme is shown in the Basic calculator example.
Variables, Functions and Other Enhancements
Variables and Functions
Let's consider an expression: a+cos(pi) where a and pi are variables and cos is the cosine function. As defined above, the Primary()
function is used to parse operands. In general, it should parse names and digits separately. Also, the Name
parser should separate variables' and functions' names. The difference between cos(pi)
and cosPI
is that the first one is a function and the second one is a variable. The trick is that there is no actual "function" concept in this calculator. All functions are treated as operators. For instance, sin(x)
is treated as a unary operator and log(x,y)
as binary.
Each character sequence that is not a function (x, y1, sinX, etc.) is treated as a variable. The best way to store variables is in a Dictionary <string, double>
collection. Therefore if the Primary()
function discovers that the current token is a letter, it calls an addition function that reads the whole sequence of characters until an "escape" token is reached. In our example, a is a letter, but the next token is "+". This token cancels reading the sequence. First, the parser checks if "a" is a function or a variable. Then it retrieves "a" from memory (the dictionary) and pushes the value of the "a" variable into the stack.
In the case of a function (in our example, a+cos(pi) ), the parser reads the "c" token and does the same thing as was done with the variable: it reads "c", "o", "s", finds the escape "(" character and locates the cos function in the functions list. Then the parser calls (remember the recursion?) Primary()
to parse the function's parameters. For example: cos(pi), log(10, abs( cos(pi) )), etc.
Variables Assignment
Therefore there are stored variables (pi, e) and there should be variables assignment: a=b=10^2. The "=" operator calls Parse()
recursively: a=Parse( b=Parse(10^2) )
Multiplication
In mathematical expressions, multiplication is sometimes omitted. For example: the 10*x expression could be replaced with 10x. Let's define all cases in which multiplication could be omitted: x*(y), (y)*x, (y)*(x), x*f(x). When the parser finds a number, a variable or a right parenthesis, it calls the TryInsertMultiply()
function that pushes the "*" operator in the stack if multiplication between the tokens was omitted.
Rightside Operators
One of the unary rightside operators in mathematics is the Factorial operator. Factorial is the product of all positive integers from one up to n and including a given integer. Factorial zero is assigned the value of one, factorial n (n!) is 1*2*...*(n1)*n. To check if the next token is a rightside operator, the TryRightSideOperator()
function is called. Argument separators in a multiargument function are also treated as a rightside operators, i.e. log(2,4).
Power Operation
There is a basic math rule which I had forgotten. The power operator could not be evaluated the same way as multiplication or addition operators are evaluated. 3^4^5 = 3^(4^5), but 3*4*5 = (3*4)*5 or 3*(4*5). This is called associative operation. When the Compare()
function compares two power operators, it returns "1". This means that the current operator (the one that is on the top of the stack) is not processed.
Using the Code
There is one partial class Calculator
divided into four files: Parser, Processor, Token and Variable.
 Parser contains general and parse functions
 Processor contains math operations' functions
 Token contains tokens' (operations and functions) constants. It also contains "Is...()" functions, which determine whether the token is a digit, a function, an operator or a variable
 Variable contains stored variables' subroutines
Points of Interest
The next step is to slightly modify the code and make the calculator able to solve logical expressions.
History
 Power operation bug fixed  15 January 2008
 Release  23 October 2007