Polish Notation and Conversion Algorithm

By -

If you type in "Polish Notation" in Google search bar what you get is "a system of formula notation without brackets or special punctuation, frequently used to represent the order in which arithmetical operations are performed in many computers and calculators." So what does it mean?



     Actually, It's simple. Consider the following arithmetic expression,
                  (A + B) * C
    
If you remove the parenthesis from the expression, it gives complete different sense. So here it is essential to use parenthesis to remove ambiguity,  Is there any way to reduce the need of parenthesis or special punctuation? Here comes the Polish Notation and Reverse Polish Notation. 

Consider another simple example,
                A + B
This is called infix notation since operator '+' is in between 'A' and 'B'.
Without altering the meaning we can write postfix notation(Reverse Polish Notation) as,
                    AB+
And prefix notation(Polish Notation) as
                   +AB

How this removes need of parenthesis and punctuation. Let's look at the earlier considered expression
           (A + B) * C

 Direct conversion to postfix notation goes like this,
              (A + B) * C   //Parenthesized portion of expression get the highest precedence so convert it first
               (AB+)*C //You can now consider converted  expression as single chunk of expression
               (AB+)C* //No need of parenthesis. Removing it doesn't create ambiguity in meaning
              AB+C*

Similarly, to prefix notation
            (A + B) * C
            (+AB) * C
            *(+AB)C
            *+ABC

Now considering the cases of the same precedence but different associativity,
(Conversion from infix to postfix for two cases is done here. You can do exercise on infix to prefix conversion)
A + B - C //left associativity
(A + B) - C //operation with left operator is done first
(AB+) - C
AB+C-

A ^ B ^ C //right associativity
A ^ (B ^ C) //operation with right operator is done first
A ^ (BC^)
ABC^^
  


Did you get the difference due to associativity?


Let's apply it for a giant,


Consider an infix expression, 
A + B * C + (D * E + F) ^ G
To postfix notation (strike is the expression going to be converted, and underline is postfix expression)
A + B * C + (D * E + F) ^ G
A + B * C + (DE* + F) ^ G
A + B * C + DE*F+ ^ G
A + B * C + DE*F+G^
A + BC* + DE*F+G^
ABC*+ + DE*F+G^
ABC*+DE*F+G^+

I recommend reader to convert the expression to prefix expression by their own.

Now dive into the conversion algorithm. We will discuss the stack implementation of the conversion.

First of all, consider the conversion from infix to postfix notation
Infix to Postfix Conversion
We will discuss the stack implementation of the conversion. We require a stack where operator are piled up and an output string(postfix expression)
Points to be noted:
  • Here operand means alphanumeric terms involved in the expression.
  • Operands are immediately appended in output expression.
  • Operation on higher precedence operator need to be done first and since in stack operation is possible only on top, higher precedence operator need to be on top of stack.
  • Parenthesis gets highest precedence. Hence '(' is immediately pushed on the stack.
  • '(' can only be popped by ')' i, e. braces need to be balanced. So parenthesized portion of expression need to be completely converted into postfix before traversing after ')'
  • In the case of equal precedence associativity of operator need to be considered. If the operator is left associative operation on left operator need to be done first, opposite in the case of right associativity.
    For example, in expression A + B + C
                                    When second '+' is encountered stack top is '+'. Since the operator is left associative operation on first '+' need to be done first. So top is popped and appended to the output. This need to be done until currently reading operator has equal precedence and right associative or reading operator has higher precedence than that of stack top.
  • After string traversing is finished. All stack contents need to be appended to the output.


Algorithm:
INPUT: A valid infix expression, (infixExpr)
OUTPUT: Corresponding postfix expression of input infix expression (postfixExpr)
       
STEP 1: Declare stack and output postfix string
        
STEP 2: for i = 0 to infixExpr.length() repeat STEP 3 - 6

STEP 3: if infixExpr[i] is operand append it to output

STEP 4: if infixExpr[i] is operator then
                if operatorStack is empty push the infixExpr[i] to stack
                if operatorStack.top() == '(',
                    this need to be popped by ')' so simply push infixExpr[i] in operatorStack
                if infixExpr[i] operator has lower precedence than that of operatorStack.top()
                or (they have equal precedence and are left associative) then
                    pop operatorStack top and append it to output.
                This need to be done until above condition doesn't satisfy

STEP 5: if infixExpr[i] is '(', push it to stack
STEP 6: if infixExpr[i] is ')', pop all stack content until '(' and append it to output. Pop up '('.
STEP 7: After string traversal is finished, pop all stack content until stack is empty.
STEP 8: Return postfix expression.

The function used in following snippets are implemented on the complete program given at the end.

string infixToPostfix(string infixExpr) {
    //Define a stack to store operator and output string initialized to empty string
    stack<char> operatorStack;
    string postfixExpr = "";

    //Iterate across the input string
    for (int i = 0; i < infixExpr.length(); i++) {
        //Skip white spaces in infixExpr
        if (infixExpr[i] == ' ')
            continue;
        //if infixExpr[i] is operand append it to output postfixExpr
        else if (isOperand(infixExpr[i]))
            postfixExpr += infixExpr[i];
        else if (isOperator(infixExpr[i])) {
            while ((!operatorStack.empty() && operatorStack.top() != '('
                    && (hasLowerPrecedence(infixExpr[i], operatorStack.top()) ||
                        (ofEqualPrecedence(infixExpr[i], operatorStack.top()) && !isRightAssociative(infixExpr[i]))))) {
                postfixExpr += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(infixExpr[i]);
        }
    
        else if (infixExpr[i] == '(')
            operatorStack.push(infixExpr[i]);

        else if (infixExpr[i] == ')') {
            while (operatorStack.top() != '(') {
                postfixExpr += operatorStack.top();
                operatorStack.pop();
            }
            //No need to append '(' to prefixExpr(output). Just pop it out of stack.
            operatorStack.pop();
        }
    }

    while (!operatorStack.empty()) {
        postfixExpr += operatorStack.top();
        operatorStack.pop();
    }

    //Kaam tamam. Return prefixExpr
    return postfixExpr;
}

Infix to Prefix Conversion
This is almost similar to infix to postfix conversion.
Here,
  • Traversal need to be done from back to front on infix expression
  • Push Pop operation of operator stack is similar to that of infix to postfix conversion but in the case of equal precedence, we have to push pop operator when an operator is right associative.
  • The output will be reverse of the expected. So the reversal of output needs to be done. Here reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) function from algorithm class is used.
Following is the c++ function for infix to prefix conversion


string infixToPrefix(string infixExpr) {
    stack<char> operatorStack;
    string prefixOutput = "";

    for(int i = infixExpr.length() - 1; i >= 0; i--) {
        if(infixExpr[i] == ' ')
            continue;
        else if(isOperand(infixExpr[i]))
            prefixOutput += infixExpr[i];
        else if(isOperator(infixExpr[i])) {
            while(!operatorStack.empty() && operatorStack.top() != ')'
                    && (hasLowerPrecedence(infixExpr[i], operatorStack.top()) ||
                        (ofEqualPrecedence(infixExpr[i], operatorStack.top()) && isRightAssociative(infixExpr[i])))) {
                /**-------------Notice the difference in condition of while loop than that of infixToPostfix--------------*/
                prefixOutput += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(infixExpr[i]);
        }
        //')' will be encountered first so push it to operator stack just opposite to infixToPostfix
        else if(infixExpr[i] == ')')
            operatorStack.push(infixExpr[i]);
        //Here pop and append until ')' doesn't appear at the top
        else if(infixExpr[i] == '(') {
            while(operatorStack.top() != ')') {
                prefixOutput += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.pop();
        }
    }
    while(!operatorStack.empty()) {
        prefixOutput += operatorStack.top();
        operatorStack.pop();
    }
    //reverse the output. Used reverse() from  <algorithm>
    reverse(prefixOutput.begin(), prefixOutput.end());
    return prefixOutput;
}

Postfix to Infix Conversion

To do the reverse of infix to postfix, we require a stack which can hold expression as its data member i.e, stack of type.  When an operator is seen on postfix expression, it will be infixed between latest two operand which are top two elements of stack and pop back into stack which in turn now can works as another operand.

Algorithm:
INPUT: A valid postfix expression (postfixExpr)
OUTPUT: Corresponding infix expression of input postfix expression (infixExpr)

STEP 1: Create new string type stack
STEP 2: for i = 0 to postfixExpr.length() repeat STEP 3 - 4
STEP 3: if postfixExpr[i] is operand push it to stack
STEP 4: if postfixExpr[i] is operator pop top two elements of stack and make an infix                              expression with the operator and push the expression on the stack
STEP 5: After 'for' loop if Stack size is 1 then return stack top which is required infix expression. Else given expression is not write


string postfixToInfix(string postExpression) {
    stack<string> exprStack;
    for(int i = 0; i < postExpression.length(); i++) {
        if(postExpression[i] == ' ')
            continue;
        else if(isOperand(postExpression[i]))
            exprStack.push(string(1, postExpression[i]));
        else if(isOperator(postExpression[i])) {
            string top = exprStack.top();
            exprStack.pop();
            string nextTop = exprStack.top();
            exprStack.pop();
            exprStack.push("(" + nextTop + postExpression[i] + top + ")");
        }
    }
    return exprStack.size() == 1 ? exprStack.top() : throw 1;
}

Prefix to Infix Conversion

Unlike postfix to infix conversion, here traversal in prefix expression is done from back to front.


string prefixToInfix(string prefixExpression) {
    stack<string> exprStack;
    for(int i = prefixExpression.length() - 1; i >= 0; i--) {
        if(prefixExpression[i] == ' ')
            continue;
        else if(isOperand(prefixExpression[i]))
            exprStack.push(string(1, prefixExpression[i]));
        else if(isOperator(prefixExpression[i])) {
            string top = exprStack.top();
            exprStack.pop();
            string nextTop = exprStack.top();
            exprStack.pop();
            exprStack.push("(" + top + prefixExpression[i] + nextTop + ")");
        }
    }
    return exprStack.size() == 1 ? exprStack.top() : throw 1;
}

Here is the complete program of infix to postfix, infix to prefix, postfix to infix, prefix to infix, prefix to postfix and postfix to prefix. You are free to copy, modify and compile it.


/**
    A C++ program for polish conversion.

    @author Sagar Sapkota
*/

#include <iostream>
#include <stack>
#include <string>
#include <algorithm> //used for reversing string in infix to prefix  conversion

using namespace std;

//Function prototypes

/**
    This function converts provided valid infix expression into postfix expression and returns it.

    @param string infixExpr --> A valid infix expression of string type
    @return string postfixExpr --> Corresponding postfix expression of infix expression received as parameter
*/
string infixToPostfix(string);

/**
    This function converts provided valid infix expression into prefix expression and returns it.

    @param string infixExpr --> A valid infix expression of string type
    @return string prefixExpr --> Corresponding prefix expression of infix expression received as parameter
*/
string infixToPrefix(string);

/**
    This function converts provided valid postfix expression into infix expression and returns it.

    @param string postfixExpr --> A valid postfix expression of string type
    @return string infixExpr --> Corresponding infix expression of postfix expression received as parameter
*/
string postfixToInfix(string);

/**
    This function converts provided valid prefix expression into infix expression and returns it.

    @param string prefixExpr --> A valid prefix expression of string type
    @return string infixExpr --> Corresponding infix expression of prefix expression received as parameter
*/
string prefixToInfix(string);

/**
    Function to convert prefix to postfix expression
    Uses function prefixToInfix(string) and infixToPostfix(string) for conversion
    !-------- Suggest me if you have better algorithm ----------!

    @param string prefixExpr
    @return string postfixExpr
*/
string prefixToPostfix(string);

/**
    Function to convert postfix to prefix expression
    Uses function postfixToInfix(string) and infixToPrefix(string) for conversion as subroutines

    @param string postfixExpr
    @return string prefixExpr
*/
string postfixToPrefix(string);

/**
    Function to check precedence

    @param 1. (char) optr1 --> in polish conversion currently reading operator in input expression
    @param 2. (char) optr2 --> in polish conversion operator at top of stack
    @return true --> if precedence optr1 < precedence optr2 else false
*/
bool hasLowerPrecedence(char, char);

/**
    Checks if operator has equal precedence.
    Required when stack top and reading operator has equal precedence
    then to check associativity of the operator

    @param 1. (char) optr1 --> in polish conversion currently reading operator in input expression
    @param 2. (char) optr2 --> in polish conversion operator at top of stack
    @return true --> if two operator has equal precedence
*/
bool ofEqualPrecedence(char, char);

/**
    Checks if parameter is operator or not

    @param (char) symbol --> character symbol to check if it is a operator
    @return true --> if symbol is operator
*/
bool isOperator(char);

/**
    Checks if parameter is operand or not

    @param (char) symbol --> character symbol to check if it is a operand
    @return true --> if symbol is operand
*/
bool isOperand(char);

/**
    Used by precedence checking function for comparing weight of operator

    @param (char) optr --> operator whose weight is required
    @return (int) weight --> integer value representing operator weight
*/
int getOperatorWeight(char symbol);

/**
    @param (char) optr --> operator to check associativity
    @return (bool) true --> if operator symbol is right associative else false
*/
bool isRightAssociative(char optr);

//main function
int main() {
    cout << "1 --> Infix to Postfix\n";
    cout << "2 --> Infix to Prefix\n";
    cout << "3 --> Postfix to Infix\n";
    cout << "4 --> Prefix to Infix\n";
    cout << "5 --> Postfix to Prefix\n";
    cout << "6 --> Prefix to Postfix\n";

    cout << "\nEnter your choice: ";
    int choice;
    cin >> choice;
    cin.ignore();
    string expression;
    switch(choice) {
    case 1:
        cout << "Enter infix expression: ";
        getline(cin, expression);
        cout << "Postfix Expression: " << infixToPostfix(expression) << endl;
        break;
    case 2:
        cout << "Enter infix expression: ";
        getline(cin, expression);
        cout << "Prefix Expression: " << infixToPrefix(expression) << endl;
        break;
    case 3:
        cout << "Enter postfix expression: ";
        getline(cin, expression);
        cout << "Infix Expression: " << postfixToInfix(expression) << endl;
        break;
    case 4:
        cout << "Enter prefix expression: ";
        getline(cin, expression);
        cout << "Infix Expression: " << prefixToInfix(expression) << endl;
        break;
    case 5:
        cout << "Enter postfix expression: ";
        getline(cin, expression);
        cout << "Prefix Expression: " << postfixToPrefix(expression) << endl;
        break;
    case 6:
        cout << "Enter prefix expression: ";
        getline(cin, expression);
        cout << "Postfix Expression: " << prefixToPostfix(expression) << endl;
        break;
    default:
        cout << "Wrong choice!!!!" << endl;
    }
    return 0;
}


//Implementation
string infixToPostfix(string infixExpr) {
    //Define a stack to store operator and output string initialized to empty string
    stack<char> operatorStack;
    string postfixExpr = "";

    //Iterate across the input string
    for (int i = 0; i < infixExpr.length(); i++) {
        //Skip white spaces in infixExpr
        if (infixExpr[i] == ' ')
            continue;
        //if infixExpr[i] is operand append it to output postfixExpr
        else if (isOperand(infixExpr[i]))
            postfixExpr += infixExpr[i];
        /**
            if infixExpr[i] is operator then
                if operatorStack is empty push the infixExpr[i] to stack
                if operatorStack.top() == '(',
                    this need to be popped by ')' so simply push infixExpr[i] in operatorStack
                if infixExpr[i] operator has lower precedence than that of operatorStack.top()
                or (they have equal precedence and are left associative) then
                    pop operatorStack top and append it to output.
                This need to be done until above condition doesn't satisfy
        */
        else if (isOperator(infixExpr[i])) {
            while ((!operatorStack.empty() && operatorStack.top() != '('
                    && (hasLowerPrecedence(infixExpr[i], operatorStack.top()) ||
                        (ofEqualPrecedence(infixExpr[i], operatorStack.top()) && !isRightAssociative(infixExpr[i]))))) {
                postfixExpr += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(infixExpr[i]);
        }
        /**
            '(' is of highest precedence, push it to operator stack
              It is only popped by ')'. This means expression inside parenthesis need
              to be converted into equivalent postfix first. So you can assume
              stack above '(' a virtual new stack.
        */
        else if (infixExpr[i] == '(')
            operatorStack.push(infixExpr[i]);

        /**
            Whenever infix[i] == ')' A small expression inside infixExpr(enclosed inside '(' and ')')
            is assumed to be completed. So finish the job of that small expression until '('
            doesn't appear in operatorStack.top().
        */
        else if (infixExpr[i] == ')') {
            while (operatorStack.top() != '(') {
                postfixExpr += operatorStack.top();
                operatorStack.pop();
            }
            //No need to append '(' to prefixExpr(output). Just pop it out of stack.
            operatorStack.pop();
        }
    }

    /**
        Loop has been finished. Means we have completed our traversal on infixExpr.
        So append operatorStack content to output postfixExpr.
    */
    while (!operatorStack.empty()) {
        postfixExpr += operatorStack.top();
        operatorStack.pop();
    }

    //Kaam tamam. Return prefixExpr
    return postfixExpr;
}

/**
    Almost similar to infix to postfix conversion
    Steps involved
        -->Traverse from end to begin of infixExpr
        -->push pop operation of operator stack is similar to that of infix to postfix conversion
            but in case of equal precedence we have to push pop operator when
            operator is right associative.
        -->Output will be reverse of the expected.
*/
string infixToPrefix(string infixExpr) {
    stack<char> operatorStack;
    string prefixOutput = "";

    for(int i = infixExpr.length() - 1; i >= 0; i--) {
        if(infixExpr[i] == ' ')
            continue;
        else if(isOperand(infixExpr[i]))
            prefixOutput += infixExpr[i];
        else if(isOperator(infixExpr[i])) {
            while(!operatorStack.empty() && operatorStack.top() != ')'
                    && (hasLowerPrecedence(infixExpr[i], operatorStack.top()) ||
                        (ofEqualPrecedence(infixExpr[i], operatorStack.top()) && isRightAssociative(infixExpr[i])))) {
                /*-------------Notice the difference in condition of while loop than that of infixToPostfix--------------*/
                prefixOutput += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(infixExpr[i]);
        }
        //')' will be encountered first so push it to operator stack just opposite to infixToPostfix
        else if(infixExpr[i] == ')')
            operatorStack.push(infixExpr[i]);
        //Here pop and append until ')' doesn't appear at the top
        else if(infixExpr[i] == '(') {
            while(operatorStack.top() != ')') {
                prefixOutput += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.pop();
        }
    }
    while(!operatorStack.empty()) {
        prefixOutput += operatorStack.top();
        operatorStack.pop();
    }
    //reverse the output. Used reverse() from  <algorithm>
    reverse(prefixOutput.begin(), prefixOutput.end());
    return prefixOutput;
}


string postfixToInfix(string postExpression) {
    stack<string> exprStack;
    for(int i = 0; i < postExpression.length(); i++) {
        if(postExpression[i] == ' ')
            continue;
        else if(isOperand(postExpression[i]))
            exprStack.push(string(1, postExpression[i]));
        else if(isOperator(postExpression[i])) {
            string top = exprStack.top();
            exprStack.pop();
            string nextTop = exprStack.top();
            exprStack.pop();
            exprStack.push("(" + nextTop + postExpression[i] + top + ")");
        }
    }
    return exprStack.size() == 1 ? exprStack.top() : throw 1;
}

string prefixToInfix(string prefixExpression) {
    stack<string> exprStack;
    for(int i = prefixExpression.length() - 1; i >= 0; i--) {
        if(prefixExpression[i] == ' ')
            continue;
        else if(isOperand(prefixExpression[i]))
            exprStack.push(string(1, prefixExpression[i]));
        else if(isOperator(prefixExpression[i])) {
            string top = exprStack.top();
            exprStack.pop();
            string nextTop = exprStack.top();
            exprStack.pop();
            exprStack.push("(" + top + prefixExpression[i] + nextTop + ")");
        }
    }
    return exprStack.size() == 1 ? exprStack.top() : throw 1;
}

string prefixToPostfix(string prefixExpr) {
    return infixToPostfix(prefixToInfix(prefixExpr));
}

string postfixToPrefix(string postfixExpr) {
    return infixToPrefix(postfixToInfix(postfixExpr));
}

bool isOperand(char symbol) {
    return (symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z') || (symbol >= '0' && symbol <= '9');
}

bool isOperator(char symbol) {
    return (symbol == '^' || symbol == '/' || symbol == '*' || symbol == '+' || symbol == '-');
}

bool hasLowerPrecedence(char operator1, char operator2) {
    return getOperatorWeight(operator1) < getOperatorWeight(operator2);
}

bool ofEqualPrecedence(char operator1, char operator2) {
    return getOperatorWeight(operator1) == getOperatorWeight(operator2);
}

int getOperatorWeight(char symbol) {
    int weight;
    switch (symbol) {
    case '+':
    case '-':
        return 1;
    case '/':
    case '*':
        return 2;
    case '^':
        return 3;
    default:
        return 0;
    }
}

bool isRightAssociative(char optr) {
    return (optr == '^');
}

Comments

  1. UnknownJune 24, 2017 at 1:27 AM

    Thanks for this.

    ReplyDelete
  2. UnknownJune 24, 2017 at 2:03 AM

    that was interesting,your work and knowledge was amazing . keep going

    ReplyDelete
  3. UnknownJune 24, 2017 at 2:17 AM

    Informative article. Thank you

    ReplyDelete
  4. UnknownJune 24, 2017 at 2:56 AM

    Polish Notation frequently used to represent the order in which arithmetical operations are performed in many computers and calculators. It's a nice algorithm.

    ReplyDelete
  5. UnknownJune 24, 2017 at 3:46 AM

    very useful. I am most interested about this.

    ReplyDelete

Post a Comment

Need Help? Make a comment below & we'll help you out... :)

Popular posts from this blog

How to write a cover letter to register free .com.np in Nepal

By -
Image
Hello guys, Today I have written this post to help you guys write a cover letter which is very essential for .com.np domain registration and without which you cannot apply for domain registration. You must write a cover letter to register a free .com.np domain. Before you had to submit the cover letter at Mercantile Communications Pvt. Ltd office located at Hiti Pokhari, Durbar Marg, Kathmandu, Nepal. But now you must submit the cover letter during the online domain request process.
You can find the process to register .com.np here. How To Register .com.np domain for free [NEW]
The cover letter I submitted while registering for www.sunuwarbishal.com.np for my friend can be seen in the image below.

The sample cover letter format for registering free .com.np is:

Date Here To, The Host Master Mercantile Communication Pvt.Ltd DurbarMarg, Kathmandu Nepal
Subject: About Domain Registration
Dear Sir/Madam, I would like to request you for the domain registration of http://www.YourDomainName.co…
Read more

Add a Comment Form Message on Blogger

By -
Image
You can actually add a custom message to the Comment form in blogger without any codes. You can add sweet little messages or any messages regarding your comment guidelines. So if you are wondering about how to add a custom message above the comment form you see on the other websites, then you have visited the correct post. Comment form message feature is available in Blogger itself and I will guide you through the steps required to add the custom comment form message step by step.
Here are the steps. Let's do this.
Step 1: In your Blogger Dashboard, click on "Settings" and select "Posts, comments and sharing".

Step 2: Scroll down until you see the text "Comment Form Message". Then click on "Add" and write your own custom message that you wish to appear before every Comment form. Just click on "Save Settings" on the top-right corner after you write your custom message.

After you add your own custom comment message, it appears in the …
Read more

How to Activate Windows Free of Cost

By -
Image
As many people are facing the problems of windows activation, I have come across a solution by which you can activate the windows for free of cost. The problems in unactivated windows are that activate windows notice appears time to time which is a bit irritating and also the watermark saying activate windows appears on the right-bottom corner. So, keeping this in mind the activation of windows becomes essential as it is irritating to use unactivated windows. I have come across a software called KMSAuto which is available on the internet and so I decided to share you the software and the steps to activate the windows free of cost. Yes, you heard it right free of cost i.e you don't need to waste a single penny. Using this software, you can also activate the Microsoft Office free of cost.
If you have problems with Microsoft Office activation, you can view this post here which has stepwise methods with pictures which can help you out. How to Activate Microsoft Office Free of Cost
Now l…
Read more