Polish Notation in Data Structure

In Polish notation, the operator is placed before the operands. it is also known as prefix notation. generally, we use an operator between the two operands like x + y but in Polish notation, we use the operators before the operands like +xy.

this notation is given by a mathematician Jan Lukasiewicz in 1924.

What is Reverse polish notation?

in reverse Polish notation, the operator is placed after the operands like xy+, and it is also called Postfix notation.

In both Polish and reverse Polish notation we don’t require the parentheses because all the operators are arranged in their precedence associativity rule.

^   >  *  =  /  >  –  =  +

Types of Notations.

In general, we have three types of notation. infix, postfix, and prefix.

x+ y = Infix

+xy = Prefix

xy+ = Postix

let’s see how to convert Infix to the prefix (  Polish ) and postfix ( reverse Polish ) notation.

Conversion from Infix to postfix expression.

these are some rules that we need to follow to convert an expression from infix to postfix.

If the expression has parentheses then the part inside the parentheses will be converted first.

operations will be converted in order of their precedence and associativity.

we take the converted operations as a single operand and place them into the [ ] bracket.

Let’s say we have an expression

P + Q ^ R + S * T / ( U – V )

first, we convert the expression that is inside the parentheses.

P + Q ^ R + S * T / [ U V-]

Now the ^ operator has higher priority than the first we convert this.

P + [QR^ ]+ S * T / [ UV-]

then the * and / operator has higher priority so we here apply the FIFO rule means the first cone is first out. so the * operators have come first so first, we convert this.

P + [QR^ ]+ [ST*] / [ UV-]

then we convert / operator.

P + [QR^ ]+ [ST* UV – /]

then we use the convert + operator that comes first.

[PQR^+]+ [ST* UV – /]

and then we convert the + operator.

PQR^+ST* UV – /+

so this is the postfix expression of the infix expression.

Conversion from Infix to prefix expression.

here the rules are the same as we follow above in the postfix conversion.

let’s say we have an expression

P + Q ^ R + S * T / ( U – V )

so the steps are as follows to convert this infix expression into a prefix expression.

P + Q ^ R + S * T / [ -UV ]

P + [^QR] + S * T / [ -UV ]

P + [^QR] + [*ST] / [ -UV ]

P + [^QR] + [*ST-UV/ ]

[+P^QR] + [/*ST-UV ]

++P^QR/*ST-UV

So this is the prefix expression of the Infix expression.

How to Evaluate a postfix expression

let’s say we have a postfix expression

4 3 2 + 2 ^ * 5 – 

to evaluate this postfix notation we traverse this expression from left to right and whenever we will find an operator we take the previous two operands and apply the operator to them.

so in the above expression first we find the + operator then the previous two operands 3 and 2 and apply on them the + operator.

so the new expression is

3 [5] 2 ^ * 5 –

after that, we find the ^ operator then we apply this operator to the previous two operands. and this condition will run until we got a single operand. as you see in the given below image.

How to Evaluate a prefix expression.

let’s say we have a postfix expression

– * 4 ^ + 3 2 2 5

to evaluate this prefix expression first we scan this expression from right to left and whenever we will find an operator we apply it on the next two operands. as you see in the image given below.

Program to convert Infix to postfix using stack in Python.

class Stack:

    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            raise EmptyStackError("Stack is empty")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise EmptyStackError("Stack is empty")
        return self.items[-1]

    def display(self):
        print(self.items)


def infix_to_postfix(infix):
    postfix = ""
    st = Stack()

    for symbol in infix:
        if symbol == ' ' or symbol == '\t':
            continue
        if symbol == '(':
            st.push(symbol)
        elif symbol == ')':
            next = st.pop()
            while next != '(':
                postfix = postfix + next
                next = st.pop()
        elif symbol in "+-*/%^":
            while not st.is_empty() and precedence(st.peek()) >= precedence(symbol):
                postfix = postfix + st.pop()
            st.push(symbol)
        else:
            postfix = postfix + symbol

    while not st.is_empty():
        postfix = postfix + st.pop()
    return postfix


def precedence(symbol):
    if symbol == '(':
        return 0    elif symbol in '+-':
        return 1    elif symbol in '*/%':
        return 2    elif symbol == '^':
        return 3    else:
        return 0

def evaluate_postfix(postfix):
    st = Stack()

    for symbol in postfix:
        if symbol.isdigit():
            st.push(int(symbol))
        else:
            x = st.pop()
            y = st.pop()

            if symbol == '+':
                st.push(y + x)
            elif symbol == '-':
                st.push(y - x)
            elif symbol == '*':
                st.push(y * x)
            elif symbol == '/':
                st.push(y / x)
            elif symbol == '^':
                st.push(y ** x)

    return st.pop()


#############
while True:
    print("Enter infix expression ( q to quit ) ", end='')

    expression = input()
    if expression == 'q':
        break
    postfix = infix_to_postfix(expression)
    print("Postfix expression is : ", postfix)
    print("Value of expression : ", evaluate_postfix(postfix))