Polish Notation
Algebraic expressions can be written using three separate but equivalent notations namely infix,
postfix, and prefix notations.
Infix Notation
The operator symbol is placed between its two operands in most arithmetic operations. This is
called infix expression. For example, (A + B) ; here the operator + is placed between the two
operands a and b.
Although we find it simple to write expressions in infix notation, computers find it difficult to
parse. So, the computer normally evaluates arithmetic expressions written in infix notation after
converting them into postfix notation. The stack is the primary tool used to complete the given
task in each phase.
Prefix Notation (Polish Notation)
Computers perform better when expressions are written in prefix and postfix notations.
Prefix notation refers to the notation in which the operator is placed before its two operands. For
example, if A + B is an expression in infix notation, then +AB is the equivalent expression in
prefix notation.
Postfix Notation (Reverse Polish Notation)
In postfix notation, the operator is placed after the operands. For example, if an expression is
written in infix notation as A + B, it can be written in postfix notation as AB+.
The evaluation of a postfix and prefix expressions are always performed from left to right.
Evaluation of a Postfix Expression
The following algorithm is used to evaluate the value of a postfix expression.
1. Add a ) at the end of the post fix expression
2. Scan every character of the postfix expression and repeat Steps 3 and 4 until ) is
encountered
3. If an operand is encountered, out it on the STACK.
4. If an operator O is encountered, then
1. POP the two top elements of STACK as A(topmost element) and B(next-to-top
element).
2. Evaluate B O A.
3. Push the result of evaluation on the STACK.
5. SET RESULT equal to the topmost element of the STACK.
Example
Consider the following postfix notation 8 2 3 * 8 + 2 / –. The equivalent infix expression is 8 – ((2
* 3) + 8) / 2 .
The following table shows the procedure for evaluating the expression by simulating the above
algorithm.
The final number in the stack, 1, is the value of the postfix expression.
Conversion of an Infix Expression into a Postfix Expression
For the sake of simplicity, we will only use the +, –, *, /, and % operators. The order of
precedence of these operators is as follows:
● Higher priority *, /, %
● Lower priority +, –
The algorithm below converts an infix expression to a postfix expression.
1. Push "(" on to the stack, and add ")" to the end of infix expression.
2. Repeat until each character in the infix notation is scanned
1. IF a "(" is encountered, push it on the stack.
2. IF an operand is encountered, add it to the postfix expression.
3. IF a ")" is encountered, then
1. Repeatedly pop from stack and add it to the postfix expression until a "(" is
encountered.
2. Discard the "(" . That is, remove the "(" from stack and do not add it to the postfix
expression.
4. IF an operator O is encountered, then
1. Repeatedly pop from stack and add each operator (popped from the stack) to the
postfix expression which has the same precedence or a higher precedence than
O.
2. Push the operator O to the stack.
3. Repeatedly pop from the stack and add it to the postfix expression until the stack
is empty.
Example
Convert the infix expression A + ( B * C ) into postfix expression.
Recursion Using Stack with Example
A function that calls itself is called a recursive function and this technique is called recursion. A
recursive function will call itself until a final call that does not require a call to itself is made. It
takes advantage of the system stack to temporarily store the calling function’s return address
and local variables.
There are two major cases in any recursive solution. They are
Base case in which the problem is simple enough to be solved directly without the need for any
more calls to the same function
Recursive case
The problem at hand is initially subdivided into simpler sub-parts.
The function calls itself again, but this time with sub-parts of the problem obtained in the first
step.
The final result is obtained by combining the solutions of simpler sub-parts.
A recursive function is said to be well-defined if it has the following two properties:
There must be a base criteria in which the function doesn’t call itself.
Every time the function is called itself, it must be closer to the base criteria.
Factorial Function
To illustrate recursive functions, consider calculating the factorial of an integer.
The product of the positive integers from 1 to n is called n factorial denoted by n! . To find n!,
multiply the number by the factorial of the number that is one less than the number.
That is, n! = n * (n - 1)!
Assume we need to find the value of 5!.
Then, 5! = 5 * 4!, where 4! = 4 * 3!
Therefore, 5! = 5 * 4 * 3!
Expanding further, we get 5! = 5 * 4 * 3 * 2 * 1!We can now write a recursive function that
computes the factorial of a number. Here the base case is when n = 1, because the result will be
1 as 1! = 1. The recursive case of the factorial function will call itself, but with a smaller value of
n, as factorial(n) = n factorial (n–1).
Working of the factorial function using recursion
Example: Factorial of a given number
#include <stdio.h>
int Fact(int);
int main()
{
int num, val;
//read a number from the user
printf("Enter the number: ");
scanf("%d", &num);
//call fact function
val = Fact(num);
//print result
printf("Factorial of %d = %d", num, val);
return 0;
}
//function to calculate factorial
int Fact(int n)
{
if (n == 1)
return 1;
else
return (n * Fact(n-1));
}
Output
Enter the number: 5
Factorial of 5 = 120
