Postfix Expression Evaluation using Stack

This article describes postfix expression evaluation using stack.

Operators are placed after their corresponding operands in postfix notation, also referred to as reverse polish notation. The stack data structure makes it simple to evaluate an expression written in postfix notation. In other words, you would write “3 4 +” rather than “3 + 4”.

One of the few ways to represent algebraic expressions is via postfix notation. It is used in computers because it is quicker than other notations (such as infix notation), which must be represented by parentheses.

The postfix expression follows its operands, as the name suggests. Thus, solving the infix notation is very different from the postfix evaluation method (normal notation used in daily use).

The procedure is as follows: each operand is listed first, then the operator. So, “3 + 4” would be represented as “3 4 +,” for instance. “Add 3 and 4” is what this signifies. The expression “multiply 5 and 2” would be represented as “5 2 *,” in a similar manner.

Because it is straightforward to implement using a stack data structure, postfix notation is frequently used in computer programming and in calculators. This makes it comparatively easy to evaluate complex expressions.

Examples of Postfix Expression Evaluation

Example 1:

Postfix: 236*+

Output: 20

Example 2:

Postfix: 23*6+

Output: 12

Example 3:

Postfix: 23*42/+

Output: 8

Algorithm of Postfix Expression Evaluation using Stack

A stack can be used to evaluate a postfix expression by following these steps:

Step 1: Create an empty stack.

Step 2: Iterate through the postfix expression from left to right.

Step 3: For each element in the postfix expression, do the following:

  1. If the element is an operand (a number), push it onto the stack.
  2. If the element is an operator (+, -, *, /, etc.), pop the top two elements from the stack, apply the operator to these elements, and push the result back onto the stack.

Step 4: After all elements have been processed, the result of the expression will be the single element left on the stack.

Postfix Expression Evaluation using Stack

The complexity of Postfix Expression Evaluation using Stack

Time complexity: O(n)

Space complexity: O(n)

Python Code

def evaluate_postfix(postfix_expr):
    stack = []
    operators = set(['+', '-', '*', '/', '%', '^'])
    
    for elem in postfix_expr:
        if elem not in operators:
            stack.append(float(elem))
        else:
            b = stack.pop()
            a = stack.pop()
            if elem == '+':
                stack.append(a + b)
            elif elem == '-':
                stack.append(a - b)
            elif elem == '*':
                stack.append(a * b)
            elif elem == '/':
                stack.append(a / b)
            elif elem == '%':
                stack.append(a % b)
            elif elem == '^':
                stack.append(a ** b)
                
    return stack.pop()

postfix = '236*+'  #Infix: 2 + 3 * 6
evaluate_postfix(postfix)
print('{} \t: {}'.format(postfix, evaluate_postfix(postfix)))


postfix = '23*6+'  #Infix: 2 * 3 + 6
evaluate_postfix(postfix)
print('{} \t: {}'.format(postfix, evaluate_postfix(postfix)))

postfix = '23*42/+'  #Infix: 2 * 3 + 4 / 2
evaluate_postfix(postfix)
print('{} : {}'.format(postfix, evaluate_postfix(postfix)))

Output:

236*+ 	: 20.0

23*6+ 	: 12.0

23*42/+ : 8.0

YouTube Channel: CodeCrucks

Leave a Reply

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