Question

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

150	Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

@tag-stack

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

Java

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());

	    }
	}
}

// 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()

150 - Evaluate Reverse Polish Notation

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions