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 then first we convert this.

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

then the * and / operator has higher priority so we here apply FIFO rule means the first cone 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 convert + operator that comes first.

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

and then we convert + 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 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 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 on them.

so in the above expression first we find the + operator then the previous tow 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 on 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 a python programming language.

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))

#### Also, read these posts

- What are Data Structures and algorithms
- Algorithm design and analysis
- Classification of algorithms
- How to calculate the running time of an algorithm.
- Worst Average and Best-case analysis of the algorithm.
- Big o notation
- Big o notation examples
- Linked List in Data Structures
- Traversing in Linked list
- Operations on the linked list
- Insertion in the linked list
- Deletion in a linked list
- Reversing a linked list
- Sorting a linked list
- Find and remove the loop in the linked list
- Doubly linked list
- Insertion in the doubly linked list
- Deletion in the doubly linked list
- Reversing a doubly linked list
- Circular linked list
- Insertion in the circular linked list
- Deletion in the circular linked list
- Merge two linked list
- Header linked list
- Sorted linked list
- Stack in data structures
- Queue in data structures
- Circular queue
- Dequeue in the data structure
- Priority queue
- Tree in the data structure
- Binary tree
- Array representation of the binary tree
- linked representation of a binary tree
- Traversing in the binary tree
- Inorder traversal in the binary tree
- Preorder traversal in the binary tree
- Postorder traversal in the binary tree
- Level order traversal in the binary tree
- Binary search tree
- Insertion in the binary search tree
- Deletion in the binary search tree
- Heap in data structures

## 0 Comments