Table of contents
1.
Introduction
2.
What is Polish Notation?
3.
Types of Notation
3.1.
Prefix Notation
3.2.
Postfix Notation
4.
Need of Prefix and Postfix Notation
4.1.
Conversion of infix to prefix notation 
4.2.
Conversion of infix to postfix notation
5.
Advantages of Polish Notation in Compiler Design
6.
Disadvantages of Polish Notation in Compiler Design
7.
Frequently Asked Questions
7.1.
Distinguish between infix, prefix, and postfix algebraic expressions giving examples of each.
7.2.
Why use RPN?
7.3.
Why is stack used for RPN?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Polish Notation in Compiler Design

Author Muskan Sharma
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Hey Readers!! Have you ever wondered how compilers understand the arithmetic expression that we use in our day-to-day life? Like we want to add two numbers, 8 and 5. We will write this as 8+5. But does the compiler understand this? 

Compilers find it difficult to distinguish between the operators and parentheses. But for us, it is easy to understand that we have to solve the expression first, that is, in parentheses. So, for this, we have polish notation in compiler design. 

Polish Notation in Compiler Design

This article will help you understand polish notation in compiler design, the need for polish notation in compiler design, and the conversion of notations. So let us explore polish notation in compiler design and know more about this.

What is Polish Notation?

Polish notation is also known as prefix notation. Polish notation helps compilers evaluate mathematical expressions following the order of operations using operator precedence notation, which defines the order in which operators should be evaluated, such as multiplication before addition.

In 1924 Jan Łukasiewicz thought of parenthesis-free notations, and this is where the Polish Notation was invented. 

Suppose you have to add 3 and 6 and multiply the result by 2. Normally we will write this as (3+6).2, also called infix notation, because the operators are in-between the operands. In this expression, parenthesis is a must. But when you write this in prefix notation, the expression will be .+362. In prefix notation, there is no need for the parenthesis. This expression will be evaluated as, firstly, you have to add 3 and 6 and then multiply the result with 2, which will be 18.

Types of Notation

There are two types of polish notation in compiler design. Let us look into both of these in depth.

Prefix Notation

Prefix notation is also known as polish notation. In this notation, the operators are written before the operands, not like the infix in which the operators are in-between the operands.

For example, the infix notation (5+6)*7 will be written as *+567 in prefix notation.

Postfix Notation

Postfix notation is also known as reverse polish notation. In this notation, the operators are written after the operands, not like the infix in which the operator is in-between the operands. For example, the infix notation (5+6)*7 will be written as 56+7* in postfix notation.

In the article's next section, we will discuss the need for prefix and postfix notation.

Need of Prefix and Postfix Notation

Infix notation is the traditional way of writing mathematical expressions we're all familiar with. However, it can be challenging for computers to understand and evaluate because it requires following the order of operations and using parentheses to group operations together. 

We can convert expressions into postfix or prefix notation to simplify this process for computers. This notation removes the need for parentheses and specifies the order of operations, making it easier for the computer to evaluate the expression. This is why compilers, command editors, and some calculators convert expressions into postfix or prefix notations before solving them. Once the expression is in postfix or prefix form, the computer can easily evaluate it and produce the answer.

Now let us look at the conversions infix to prefix and postfix notations.

Conversion of infix to prefix notation 

This section will help you understand the conversion of expression from infix to prefix notation.

Infix Expression:  A*B(C-D)

Symbol Stack  Expression
( (  
D ( D
- (- D
C (- DC
)   DC-
B   DC-B
* * DC-B
A * DC-BA
End of Expression   DC-BA*

The prefix notation will be: *AB-CD.


Step 1: First, reverse the infix expression.

Step 2: Do the postfix conversion steps.

Step 3: For the infix conversion, reverse the result. The reversed result will be your prefix expression.

Conversion of infix to postfix notation

Now, in this section of the article, we will be converting the infix expression to its equivalent postfix expression.

Infix Expression: P+(Q-R)*S/T

Symbol

Action

Stack

Postfix Expression

P Operand - Write in expression Stack Empty P
+ Operator - Push in the stack +  
( Opening Bracket- Push in the stack +(  
Q Operand - To expression    PQ
- Operator- Push in the stack +(-  
R Operand - To expression    PQR
) Closing Bracket- Pop everything and write in the expression UNTIL an opening bracket is popped. + PQR -
* Operator- Push in the stack +*  
S Operand - To expression    PQR - S
/ Operator- Push in the stack( Has equal precedence to topmost operator *, so * is popped and then / goes to the stack. +/ PQR - S *
T Operand - To expression    PQR - S*T
End of Expression Pop everything and write to expression   PQR - S*T/+

The postfix expression will be  PQR - S*T/+

Advantages of Polish Notation in Compiler Design

Here are some advantages of polish notation in compiler design:

  1. No need for parentheses: In polish notation, there is no need for parentheses while writing the arithmetic expressions as the operators come before the operands.
     
  2. Efficient Evaluation: The evaluation of an expression is easier in polish notation because in polish notation stack can be used for evaluation.
     
  3. Easy parsing: In polish notation, the parsing can easily be done as compared to the infix notation.
     
  4. Less scanning: The compiler needs fewer scans as the parentheses are not used in the polish notations, and the compiler does not need to scan the operators and operands differently.

Disadvantages of Polish Notation in Compiler Design

Here are some disadvantages of polish notation in compiler design:

  1. Vague: If someone sees the polish notation for the first time and doesn’t know about it. It will be very hard to understand how to evaluate the expression.
     
  2. Not used commonly: The polish notation is not commonly used in day-to-day life. These are mostly used for scientific purposes.
     
  3. Difficult for programmers: It will be difficult for programmers who need to become more familiar with polish notations to read the expression.

Frequently Asked Questions

Distinguish between infix, prefix, and postfix algebraic expressions giving examples of each.

Infix Notation: In this, the operator symbol is placed in between the operands. For example, A+B In  Prefix Notation, the operator symbol is placed before its operands. For example, + AB. In Postfix Notation, the operator symbol is placed after its operands. For example, AB+

Why use RPN?

Reverse Polish Notation (RPN) is a mathematical notation widely used and supported in computing. RPN has become popular because it offers a simplified, more efficient way to evaluate mathematical expressions.

Why is stack used for RPN?

The use of a stack is advantageous for Reverse polish notation evaluation because it simplifies the process of keeping track of operands and operators. The stack provides a convenient way to store and retrieve the operands, and the last two operands can be easily retrieved when an operator is encountered.

Conclusion

In this article, we learned about polish notation in compiler design in depth. Types of polish notations in compiler design, its conversion from infix to prefix and postfix, and the advantages and disadvantages. We hope this article helped you in knowing more about the decorator design pattern. 
 

If you want to learn more, refer to these articles: 


You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practise our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning, Ninja!

Live masterclass