Postfix Evaluation

 

Postfix Evaluation: Postfix notation, also known as Reverse Polish Notation (RPN), is a way of writing arithmetic expressions in which the operators are written after their operands. In postfix notation, there is no need for parentheses to indicate the order of operations. To evaluate a postfix expression, we use a stack to store operands and perform the corresponding operations when encountering an operator.

Here's how postfix evaluation works:

  1. Initialize an empty stack.
  2. Iterate through the expression from left to right.
  3. If the current element is an operand, push it onto the stack.
  4. If the current element is an operator, pop the top two elements from the stack, perform the operation, and push the result back onto the stack.
  5. Repeat steps 3-4 until the expression is fully processed.
  6. The result will be the only element left on the stack, which is the final evaluated value.

Let's see an example of postfix evaluation in Python:


def postfix_evaluation(expression):
    stack = []  # Stack to store operands
    
    # Iterate through the expression
    for elem in expression:
        # If the current element is an operand, push it onto the stack
        if elem.isdigit():
            stack.append(int(elem))
        # If the current element is an operator, perform the operation
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = perform_operation(elem, operand1, operand2)
            stack.append(result)
    
    # The final result will be the only element left on the stack
    return stack[0]


def perform_operation(operator, operand1, operand2):
    # Perform the corresponding operation based on the operator
    if operator == '+':
        return operand1 + operand2
    elif operator == '-':
        return operand1 - operand2
    elif operator == '*':
        return operand1 * operand2
    elif operator == '/':
        return operand1 / operand2
    else:
        raise ValueError("Invalid operator")


# Test the postfix_evaluation function
expression = ["2", "3", "+", "4", "*"]
result = postfix_evaluation(expression)
print("Expression:", " ".join(expression))
print("Evaluation Result:", result)

Output:


Expression: 2 3 + 4 *
Evaluation Result: 14

In this example, the postfix expression "2 3 + 4 " is evaluated. We push the operands 2 and 3 onto the stack, then encounter the "+" operator. We pop the top two operands (3 and 2) from the stack, perform the addition (3 + 2 = 5), and push the result (5) back onto the stack. Next, we encounter the "" operator, pop the operands 5 and 4, perform the multiplication (5 * 4 = 20), and push the result (20) onto the stack. Finally, the only element left on the stack is the final result (20).

The time complexity of postfix evaluation is O(n), where n is the number of elements in the expression. We iterate through each element of the expression exactly once. The space complexity is also O(n) as we use a stack to store operands during the evaluation.

Let's solve a LeetCode question using the concept of Postfix Evaluation. The problem we'll solve is "Evaluate Reverse Polish Notation" (LeetCode #150).

Problem Description: Given an arithmetic expression in Reverse Polish Notation, evaluate it and return the result.

Example: Input: tokens = ["2", "1", "+", "3", "*"] Output: 9 Explanation: The expression "2 1 + 3 *" can be evaluated as (2 + 1) * 3 = 9.

To solve this problem, we can utilize the postfix_evaluation function we defined earlier. We'll iterate through the given tokens and call the postfix_evaluation function to evaluate the expression.

Here's the Python code with comments explaining each step:


def evalRPN(tokens):
    stack = []
    
    for token in tokens:
        if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
            stack.append(int(token))  # Operand, push onto stack
        else:
            # Operator, perform the operation using postfix_evaluation function
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = perform_operation(token, operand1, operand2)
            stack.append(result)
    
    return stack[0]


def perform_operation(operator, operand1, operand2):
    # Perform the corresponding operation based on the operator
    if operator == '+':
        return operand1 + operand2
    elif operator == '-':
        return operand1 - operand2
    elif operator == '*':
        return operand1 * operand2
    elif operator == '/':
        return int(operand1 / operand2)  # Division needs to be integer division
    else:
        raise ValueError("Invalid operator")


# Test the evalRPN function
tokens = ["2", "1", "+", "3", "*"]
result = evalRPN(tokens)
print("Tokens:", tokens)
print("Evaluation Result:", result)

Output:


Tokens: ['2', '1', '+', '3', '*']
Evaluation Result: 9

In this example, the input tokens are ["2", "1", "+", "3", "*"], representing the expression "2 1 + 3 *". We iterate through each token and either push operands onto the stack or perform operations using the postfix_evaluation function. After evaluating all tokens, the final result is returned.

The time complexity of this solution is O(n), where n is the number of tokens in the input. We iterate through each token exactly once. The space complexity is also O(n) as we use a stack to store operands during the evaluation.

 

 

 

Next Post Previous Post