[LeetCode] 150. Evaluate Reverse Polish Notation

轉自LeetCode

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

<Solution>
直覺用 stack 來解，想法如下

• 如果是數字，就轉乘 int 放到 stack

• 如果是運算符號，就把最上面兩個數字拿出來做運算，結果再放到 stack

code如下
c++

	class Solution {
	public:
	int evalRPN(vector<string>& tokens) {
	if(tokens.empty()) {
	return 0;
	}
	stack<int> workStack;
	for(const auto &token : tokens) {
	if(token != "+"
	&& token != "-"
	&& token != "*"
	&& token != "/") {
	workStack.push(stoi(token));
	}
	else {
	int num1 = workStack.top();
	workStack.pop();
	int num2 = workStack.top();
	workStack.pop();
	if(token == "+") {
	workStack.push(num2+num1);
	}
	else if(token == "-") {
	workStack.push(num2-num1);
	}
	else if(token == "*") {
	workStack.push(num2*num1);
	}
	else if(token == "/") {
	workStack.push(num2/num1);
	}
	}
	}
	return workStack.top();
	}
	};

view raw evaluateReversePolishNotation_1.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun evalRPN(tokens: Array<String>): Int {
	val stack = mutableListOf<Int>()
	var num1 = 0
	var num2 = 0
	for(t in tokens) {
	when {
	t == "+" -> {
	num1 = stack.last()
	stack.removeAt(stack.lastIndex)
	num2 = stack.last()
	stack.removeAt(stack.lastIndex)
	stack.add(num1+num2)
	}
	t == "-" -> {
	num1 = stack.last()
	stack.removeAt(stack.lastIndex)
	num2 = stack.last()
	stack.removeAt(stack.lastIndex)
	stack.add(num2-num1)
	}
	t == "*" -> {
	num1 = stack.last()
	stack.removeAt(stack.lastIndex)
	num2 = stack.last()
	stack.removeAt(stack.lastIndex)
	stack.add(num2*num1)
	}
	t == "/" -> {
	num1 = stack.last()
	stack.removeAt(stack.lastIndex)
	num2 = stack.last()
	stack.removeAt(stack.lastIndex)
	stack.add(num2/num1)
	}
	else -> {
	stack.add(t.toInt())
	}
	}
	}
	return stack.last()
	}
	}

view raw evaluate_reversePolish_notation.kt hosted with ❤ by GitHub