# Using Stacks to evaluate prefix/postfix notation expressions (Polish notation) in C# and C++

Prefix notation (for those that do not know), is a way of writing a mathematical expression without the use of parenthesis or brackets. Also known as “Polish notation” (which was created by Jan Łukasiewicz to simplify sentential logic), it provides an easy way for computers to evaluate order of operations expressions without the use of brackets.

To start, a prefix notation example is “+34”, which would evaluate to 7 because the expression is 3+4, just in polish notation. Accordingly, there are a lot more examples of polish notation, and for the sample code posted, the algorithm will evaluate the prefix notation from a string array. In pseudo-code, the algorithm uses a stack to push and pop values in the expression and then evaluate according to the operator in the expression:

1. First we scan the expression from right to left, so we use Array.Reverse() which makes it a postfix expression like so: “43+”
2. foreach symbol or character in the expression…
3. if operand (value), then push the value onto stack
4. if operator (like +, -, *, /), then pop the two values and evaluate, and then push the current result from evaluation onto stack
5. return top of stack to display final result

For this tutorial, we will evaluate the prefix expression: /2*+345

### In C#:

```class Program
{
static void Main(string[] args)
{
Stack polishNotationStack = new Stack();//a stack of type int
//the expression will be a string array
string[] expression = { "/", "2", "*", "+", "4", "3", "5" };//first, a prefix expression
for (int i = 0; i < expression.Length; i++)//we write the prefix expression
{
Console.Write(expression[i]);
}
int result;//a result to push onto the stack after an operation was done

Console.WriteLine();//newline space
Array.Reverse(expression);//we reverse the expression to read in the characters from right to left
int n;
foreach (string c in expression)//for each string character in the array
{
if (int.TryParse(c, out n))//if the character can be converted to a number (operand)
{
polishNotationStack.Push(n);//push the number onto the stack
}
if (c == "+")//handling of operators
{
int x = polishNotationStack.Pop();
int y = polishNotationStack.Pop();
result = x + y;//evaluate the values popped from the stack
polishNotationStack.Push(result);//push current result onto the stack
}
if (c == "-")
{
int x = polishNotationStack.Pop();
int y = polishNotationStack.Pop();
result = y - x;
polishNotationStack.Push(result);
}
if (c == "*")
{
int x = polishNotationStack.Pop();
int y = polishNotationStack.Pop();
result = x * y;
polishNotationStack.Push(result);
}
if (c == "/")
{
int x = polishNotationStack.Pop();
int y = polishNotationStack.Pop();
result = y / x;
polishNotationStack.Push(result);
}

}
/*write the final result of the expression,
* which is at the top of the stack, so we use Peek()*/
Console.WriteLine("result of expression: {0}", polishNotationStack.Peek());

Console.ReadLine();
}
```

### In C++:

```#include <windows.h>
#include <iostream>
#include <fstream>
#include <stack>
#include <main.h>

using namespace std;

void WriteRPNExpression(char expression[]);
void ReverseArray (char arr []);
bool isNumber(char &exp);

int main()
{
stack<int> s;
char expression [] = "/2*+435";

WriteRPNExpression(expression);//display our rpn expression on the screen

cout<<endl;//newline space

int n;//a number ot push onto the stack
int result;//a result after performing
ReverseArray(expression);

for(unsigned int i = 0; i < 7; i++)
{

if(isNumber(expression[i])==true)
{
char c = expression[i];
n = c-'0';//parse the char to an integer
s.push(n);
}
if(expression[i]=='+')
{
int x = s.top();
s.pop();
int y = s.top();
s.pop();
result = x+y;
s.push(result);
}
if(expression[i]=='-')
{
int x = s.top();
s.pop();
int y = s.top();
s.pop();
result = y-x;
s.push(result);
}
if(expression[i]=='*')
{
int x = s.top();
s.pop();
int y = s.top();
s.pop();
result = x*y;
s.push(result);
}
if(expression[i]=='/')
{
int x = s.top();
s.pop();
int y = s.top();
s.pop();
result = y/x;
s.push(result);
}
}
cout<<"result of expression: "<<s.top();//result should be 17...

return 0;
}
void WriteRPNExpression(char arr [])
{
for(int i = 0; i < 7; i++)
{
cout<<arr[i];
}
}
void ReverseArray(char arr [])
{
int end = 6;
int start = 0;
char temp;
while(start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
bool isNumber(char &n)//pass in a char reference
{

if(!isdigit(n))//check if the char is a number...
{
return false;
}
else
return true;
}
```

## 2 comments

1. I was studying some of your content on this site and I believe this web site is very informative ! Continue putting up.

Liked by 1 person

2. […]      Exit or evaluate rpn and return final result […]

Like