## 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) |

Right-side 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 mid-1950s, to enable zero-address 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 (first-in-last-out) 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 stack-based. 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.

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; **(**10-x); 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 pseudo-C#:

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.

### Right-side Operators

One of the unary right-side 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*...*(n-1)*n. To check if the next token is a right-side operator, the `TryRightSideOperator()`

function is called. Argument separators in a multi-argument function are also treated as a right-side 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