Do you think IIT Guwahati certified course can help you in your career?
No
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.
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 asprefix 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 Łukasiewiczthought 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 arein-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 be18.
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 notationis 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:
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.
Efficient Evaluation: The evaluation of an expression is easier in polish notation because in polish notation stack can be used for evaluation.
Easy parsing: In polish notation, the parsing can easily be done as compared to the infix notation.
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:
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.
Not used commonly: The polish notation is not commonly used in day-to-day life. These are mostly used for scientific purposes.
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 aboutpolish notation in compiler designin 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: