NUHMAN.com

Introduction

Reverse Polish Notation (RPN), or postfix notation, is a mathematical notation in which operators follow their operands. For example, the expression 2 3 + in RPN represents the sum of 2 and 3. RPN eliminates the need for parentheses as operators are evaluated based on the order of operands and operations.

The task is to evaluate a mathematical expression given in RPN format, where each element of the input represents either an operand (integer) or an operator (+, -, *, /).

We will use a stack to solve this problem efficiently.

Problem Statement

You are given an array of strings tokens, where each string is either an operand (integer) or an operator (+, -, *, /). Evaluate the expression and return the result.

Function Signature:

go

func evalRPN(tokens []string) int

Approach

Key Idea:

• Stack-Based Evaluation: The idea is to use a stack where operands are pushed onto the stack. When we encounter an operator, we pop the top two operands from the stack, perform the operation, and push the result back onto the stack.

Algorithm:

1. Iterate over each token in the list.
2. If the token is an operand (i.e., an integer), push it onto the stack.
3. If the token is an operator (+, -, *, /), pop the top two elements from the stack, apply the operator, and push the result back onto the stack.
4. After processing all tokens, the stack will contain a single value, which is the result of the evaluation.

Go Implementation

go

package main

import (
	"fmt"
	"strconv"
)

func evalRPN(tokens []string) int {
	stack := []int{}

	for _, token := range tokens {
		switch token {
		case "+":
			// Pop two operands and perform addition
			b := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a+b)
		case "-":
			// Pop two operands and perform subtraction
			b := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a-b)
		case "*":
			// Pop two operands and perform multiplication
			b := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a*b)
		case "/":
			// Pop two operands and perform division
			b := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a/b)
		default:
			// It's an operand, convert string to int and push onto the stack
			num, _ := strconv.Atoi(token)
			stack = append(stack, num)
		}
	}

	// The final result is the only element left in the stack
	return stack[0]
}

func main() {
	// Example usage
	tokens := []string{"2", "1", "+", "3", "*"}
	result := evalRPN(tokens)
	fmt.Println("Result:", result) // Output: 9
}

Time and Space Complexity

OperationComplexityTimeO(n)SpaceO(n)

• Time: We traverse through the list of tokens once, and for each token, we perform constant-time operations (push, pop, arithmetic operations), so the overall time complexity is O(n), where n is the number of tokens.
• Space: We use a stack to store operands, which in the worst case will store all tokens, so the space complexity is O(n).

Example

Input:

go

tokens := []string{"2", "1", "+", "3", "*"}

Output:

9

Explanation:

1. "2" and "1" are operands, so they are pushed onto the stack: [2, 1].
2. "+" is encountered, so we pop the two operands, perform the addition 2 + 1 = 3, and push the result back onto the stack: [3].
3. "3" is an operand, so it's pushed onto the stack: [3, 3].
4. "*" is encountered, so we pop the two operands, perform the multiplication 3 * 3 = 9, and push the result back onto the stack: [9].
5. The final result is the single value left in the stack: 9.

Why This Approach Works

• Efficiency: Using a stack ensures that we can evaluate the expression in a single pass. Every operation (push, pop, arithmetic operation) is done in constant time.
• No Parentheses: Reverse Polish Notation avoids the need for parentheses because the order of operations is implicit in the token order, making it easier to evaluate.
• Handle All Operators: The implementation correctly handles the four basic arithmetic operators (+, -, *, /), and performs integer division correctly (truncating towards zero for negative results).

Conclusion

This problem illustrates the power of using a stack to evaluate expressions in Reverse Polish Notation. The solution efficiently processes each token in a single pass, making it ideal for problems involving expression evaluation. It also demonstrates the use of a hashmap for operator handling and simple arithmetic operations.