Polish Notation in Data Structures
Arithmetic Expression: An arithmetic expression is defined as several operands or data items combined using several operators. For example; a+b*(c-d) is an expression.
Operands: Operands represent the data in an expression used for the computation. We can also say that operand or operands are the items on which operation is performed. In the above example of arithmetic expression, a, b, c, and d are the operands.
Operators: Operators are the special symbols used to compute the arithmetic operation. It tells the compiler or interpreter to perform a specific task or computation between two or more operands. In the above example of arithmetic expression, +, *, and – are the operators.
There are three different and equivalent notations to represent an algebraic expression.
- Infix Notation: The operators are written in between the operands in Infix notation. It is the simplest and most commonly used notation to represent an expression. It is called infix because of the operator’s place in the expression. For example, a+b+c here, the operator '+' is placed between a and b and b and c.
We always find it simple to evaluate the expression written in infix notation. In contrast, the computer finds it difficult to parse an expression written in infix notation. To evaluate the infix operation, the computer first converts the expression in its equivalent postfix notation, and then it evaluates the same expression and gives the resulting output. The conversion of infix to postfix notation is done by using a stack.
- Prefix Notation: Prefix notation is also known as the Polish Notation. It is called a prefix because of the operator's place in the expression. The operators are written before the operands in prefix notation. For example, +ab here, the ‘+’ operator is written before a and b operands.
- Postfix Notation: Postfix notation is also known as the suffix notation and recursive Polish notation. It is called postfix because of the operator's place in the expression. The operators are written after the operands in postfix notation.
For example, ab+ here, the ‘+’ operator is written after a and b operands. The postfix notation is the most suitable notation for the computers to calculate any expression. It is the universally accepted notation for designing the CPU’s Arithmetic and Logical Unit (ALU). All the expression entered in the computer is first converted into postfix notation, stored in the stack, and then computed.