Skip to content
  • Linkedin
  • Youtube
  • Pinterest
  • Home
  • Privacy Policy
  • About
  • Contact
Programmingoneonone

Programmingoneonone

Programmingoneonone is a website that publishes daily tutorials, methods, guides, and articles on IT, Education, and technology.

  • Home
  • Human Values
  • DSA
  • IoT Tutorials
  • Interview Questions and Answers
  • Toggle search form
polish notation in data structure

Polish Notation in Data Structure

Posted on 29 May 202023 April 2023 By YASH PAL No Comments on 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.

Polish Notation in Data structures and algorithms

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.

Polish Notation in Data structures and algorithms

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))
Computer Science Tutorials, Data Structures Tutorials Tags:computer science, Data Structure

Post navigation

Previous Post: Priority queue in Data structure
Next Post: Tree in Data structure

Related Tutorials

Reading input in c programming Reading Input in a C program C Programming Tutorials
The First C Program C Programming Tutorials
Compiling C Programs C Programming Tutorials
History of c programming language HISTORY OF C Programming Language C Programming Tutorials
c character sets C Character Sets C Programming Tutorials
c programming interview questions and answers C Programming Interview Questions and Answers C Programming Tutorials

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick your Subject

  • Internet of Things
  • Data Structures/Algorithms
  • Interview Preparation
  • Human Values
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

  • Algorithms Tutorials
  • Basic Programming
  • C Programming Tutorials
  • C++ Tutorials
  • Compiler Design Tutorials
  • Computer Networks Tutorials
  • Computer Organization Tutorials
  • Computer Science Tutorials
  • Data Structures Tutorials
  • DBMS Tutorials
  • Developer Guide
  • Digital Communication
  • Digital Logic Tutorials
  • Internet of Things Tutorials
  • Internet Tutorials
  • Interview questions answers
  • Java Tutorials
  • Javascript Tutorials
  • Machine Learning Tutorials
  • Operating Systems Tutorials
  • Programming Tutorials
  • Projects
  • Tips&Tricks
  • Tools
  • VBScript Tutorials
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

Copyright © 2023 Programmingoneonone.

Powered by PressBook Blog WordPress theme