Question

Formatted question description: https://leetcode.ca/all/150.html

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

1 <= tokens.length <= 10⁴
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Algorithm

Traverse the array from front to back. When encountering a number, it is pushed onto the stack. When encountering a symbol, the two numbers on the top of the stack are taken out for operation, and the result is pushed onto the stack again, until the entire array is traversed, and the number on the top of the stack is final answer.

The biggest pit, pay attention to the order of division, the order of pop comes out is reversed, you need to reverse

regex judges the number and reports errors several times s.matches("[+-]?\\d+")) //"d" is only one digit, should be d+

Code

import java.util.Stack;

public class Evaluate_Reverse_Polish_Notation {

	public static void main(String[] args) {
		Evaluate_Reverse_Polish_Notation out = new Evaluate_Reverse_Polish_Notation();
		Solution s = out.new Solution();
		System.out.print(s.evalRPN(new String[] { "18" }));
	}

	public class Solution {
	    public int evalRPN(String[] tokens) {

	            if (tokens == null || tokens.length == 0)   return 0;
	            Stack<String> sk = new Stack<>();

	            for (int i = 0; i < tokens.length; i++) {
	                String s = tokens[i];
	                if (s.matches("[+-]?\\d+")) { //"d" is only one digit, should be d+
	                    sk.push(s);
	                }

	                else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {

	                    /*
	                        @note: order of poping!

	                        Runtime Error Message:  Line 23: java.lang.ArithmeticException: / by zero
	                        Last executed input:    ["0","3","/"]
	                    */
	                    int b = Integer.parseInt(sk.pop()); // did not check isEmpty, exception handler deal with it
	                    int a = Integer.parseInt(sk.pop());

	                    int c = 0;

	                    switch(s) {
	                        case "+":   c = a + b;      break;
	                        case "-":   c = a - b;      break;
	                        case "*":   c = a * b;      break;
	                        case "/":   c = a / b;      break;
	                        // defaut:     break;
	                    }

	                    sk.push(c + ""); // String.valueOf()
	                }

	            }

	            return Integer.parseInt(sk.pop());

	    }
	}
}

############

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stk = new ArrayDeque<>();
        for (String t : tokens) {
            if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
                stk.push(Integer.parseInt(t));
            } else {
                int y = stk.pop();
                int x = stk.pop();
                switch (t) {
                case "+":
                    stk.push(x + y);
                    break;
                case "-":
                    stk.push(x - y);
                    break;
                case "*":
                    stk.push(x * y);
                    break;
                default:
                    stk.push(x / y);
                    break;
                }
            }
        }
        return stk.pop();
    }
}

// OJ: https://leetcode.com/problems/evaluate-reverse-polish-notation/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int evalRPN(vector<string>& A) {
        stack<int> s;
        for (auto &t : A) {
            if (isdigit(t.back())) {
                s.push(stoi(t));
            } else {
                int n = s.top();
                s.pop();
                switch (t[0]) {
                    case '+': s.top() += n; break;
                    case '-': s.top() -= n; break;
                    case '*': s.top() *= n; break;
                    case '/': s.top() /= n; break;
                }
            }
        }
        return s.top();
    }
};

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        nums = []
        for t in tokens:
            if len(t) > 1 or t.isdigit():
                nums.append(int(t))
            else:
                if t == "+":
                    nums[-2] += nums[-1]
                elif t == "-":
                    nums[-2] -= nums[-1]
                elif t == "*":
                    nums[-2] *= nums[-1]
                else:
                    nums[-2] = int(nums[-2] / nums[-1])
                nums.pop()
        return nums[0]

############

class Solution(object):
  def evalRPN(self, tokens):
    """
    :type tokens: List[str]
    :rtype: int
    """
    stack = []
    for token in tokens:
      if token in ["+", "-", "*", "/"]:
        b, a = stack.pop(), stack.pop()
        if token == "+":
          res = a + b
        if token == "-":
          res = a - b
        if token == "*":
          res = a * b
        if token == "/":
          res = int(float(a) / float(b))
        stack.append(res)
      else:
        stack.append(int(token))
    return stack.pop()

func evalRPN(tokens []string) int {
	// https://github.com/emirpasic/gods#arraystack
	stk := arraystack.New()
	for _, token := range tokens {
		if len(token) > 1 || token[0] >= '0' && token[0] <= '9' {
			num, _ := strconv.Atoi(token)
			stk.Push(num)
		} else {
			y := popInt(stk)
			x := popInt(stk)
			switch token {
			case "+":
				stk.Push(x + y)
			case "-":
				stk.Push(x - y)
			case "*":
				stk.Push(x * y)
			default:
				stk.Push(x / y)
			}
		}
	}
	return popInt(stk)
}

func popInt(stack *arraystack.Stack) int {
	v, _ := stack.Pop()
	return v.(int)
}

function evalRPN(tokens: string[]): number {
    const stack = [];
    for (const token of tokens) {
        if (/\d/.test(token)) {
            stack.push(Number(token));
        } else {
            const a = stack.pop();
            const b = stack.pop();
            switch (token) {
                case '+':
                    stack.push(b + a);
                    break;
                case '-':
                    stack.push(b - a);
                    break;
                case '*':
                    stack.push(b * a);
                    break;
                case '/':
                    stack.push(~~(b / a));
                    break;
            }
        }
    }
    return stack[0];
}

using System.Collections.Generic;

public class Solution {
    public int EvalRPN(string[] tokens) {
        var stack = new Stack<int>();
        foreach (var token in tokens)
        {
            switch (token)
            {
                case "+":
                    stack.Push(stack.Pop() + stack.Pop());
                    break;
                case "-":
                    stack.Push(-stack.Pop() + stack.Pop());
                    break;
                case "*":
                    stack.Push(stack.Pop() * stack.Pop());
                    break;
                case "/":
                    var right = stack.Pop();
                    stack.Push(stack.Pop() / right);
                    break;
                default:
                    stack.Push(int.Parse(token));
                    break;
            }
        }
        return stack.Pop();
    }
}

impl Solution {
    pub fn eval_rpn(tokens: Vec<String>) -> i32 {
        let mut stack = vec![];
        for token in tokens {
            match token.parse() {
                Ok(num) => stack.push(num),
                Err(_) => {
                    let a = stack.pop().unwrap();
                    let b = stack.pop().unwrap();
                    stack.push(match token.as_str() {
                        "+" => b + a,
                        "-" => b - a,
                        "*" => b * a,
                        "/" => b / a,
                        _ => 0,
                    })
                }
            }
        }
        stack[0]
    }
}

150 - Evaluate Reverse Polish Notation

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions