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;
}

0

Advertisements

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

  1. Pingback: Convert infix to prefix notation C++/C# implementation (shunting yard method) | Bits and Pieces of Code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s