Polish Notation and Conversion Algorithm

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 == '^');
}