The purpose of this article is to show how to solve an algebraic expression as a string, by converting it from infix to postfix form and parsing the transformed string.

It is recommended that you read the following before reading it:

Prefix, infix, and postfix forms

The infix form is the most common form, because it is easier to represent. It is an expression where the operators are placed between the operands. This is where the name of the form comes from.

The prefix form, on the other hand, is an expression in which the operators are in front of the operands.

Correspondingly, the postfix form is an expression in which the operators are after the operands.

To calculate an expression written in the infix form, we need to analyze it beforehand, taking into account the precedence of operators and parentheses. Prefix and postfix forms, on the other hand, require no such analysis, since operators are written in the order they are evaluated and without parentheses.

Expressions written in the prefix or postfix form are also called parentless or Polish. They are called Polish after their author, the Polish mathematician Jan Lukasiewicz.

You can read more about the presented forms of recording algebraic expressions on Wikipedia.

Dijkstra’s algorithm.

We will use Edsger Wiebe Deikstra’s improved Deikstra algorithm to convert to postfix form.

The principle of Dijkstra’s algorithm:

1. We go through the original string;
2. When we find a number, we put it in the output string;
3. When we find an operator, we put it on the stack;
4. Push all operators that have a higher priority than the one in question from the stack to the output string;
5. If we find an opening bracket, we put it on the stack;
6. When a closing bracket is found, we push all operators before the opening bracket from the stack, and delete the opening bracket from the stack.

Implementation of Dijkstra’s algorithm

We implement the Mather class, where we define private fields infixExpr for storage of infix expression, postfixExpr for postfix expression and operationPriority, where we define the list of all operators and their priority.

In the operationPriority field the bracket (‘(‘) is defined only to avoid parsing errors later on, while the tilde (‘~’) is added to simplify further parsing and represents a unary minus.

Let’s add a private method GetStringNumber, designed for parsing integer values.

Next, create a ToPostfix method , which will convert to a reverse Polish (postfix) entry:

Algorithm for calculating a postfix record

After getting a postfix record, we need to calculate its value. To do that, we will use an algorithm that is very similar to the previous algorithm, but this one uses only one stack.

Let’s analyze how this algorithm works:

1. We go through the postfix notation;
2. When we find a number, we parse it and put it on the stack;
3. When finding a binary operator, we take the last two values from the stack in reverse order;
4. When finding a unary operator, in this case unary minus, we take the last value from the stack and subtract it from zero, since unary minus is a right-hand operator;
5. The last value, after working through the algorithm, is the solution to the expression.

Implementation of the algorithm for computing the postfix entry

Let’s create a private method Execute, which will perform the operations corresponding to the operator and return the result.

Now let’s implement the algorithm itself by creating a Calc method in which we define the following.

Testing algorithms

Let’s try running the expression 15/(7-(1+1))*3-(2+(1+1))*15/(7-(200+1))3-(2+(1+1))(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)) through the composed algorithm and see if it works correctly.

Although the algorithms implemented here work, they do not take into account spaces between characters, fractional values, check for zero in the division operation, functions are not implemented, etc., so this code is provided only as an example.