Evaluate 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.
概要
["2", "1", "+", "3", "*"]のような文字列の配列がある
解法
配列を走査する中で、
数字(operand)が来たらそのままスタックに追加
演算子(operator)が来たら、スタックから直近2要素をその演算子で計算し、両者をpopした上で計算結果をpush
時間計算量、空間計算量ともに$ O(N)
解くのにかかった時間
8分
有名な問題なのもあり、集中して一発で通せた
code:solution.cpp
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<string> st;
vector<string> op = {"+", "-", "*", "/"};
for (string t : tokens) {
if (find(op, t)) {
int a = stoi(st.top()); st.pop();
int b = stoi(st.top()); st.pop();
int val;
if (t == "+") val = b + a;
else if (t == "-") val = b - a;
else if (t == "*") val = b * a;
else if (t == "/") val = b / a;
st.push(to_string(val));
}
else st.push(t);
}
return stoi(st.top());
}
bool find(vector<string> vec, string val) {
for (string v : vec) if (v == val) return true;
return false;
}
};
時間計算量・空間計算量ともに O(N)
code:main.go
import "strconv"
func evalRPN(tokens []string) int {
var st []string
for _, token := range tokens {
if isOperator(token) {
lastIdx := len(st)-1
val := calc(token, x, y)
st = append(st, val)
} else {
st = append(st, token)
}
}
ret, _ := strconv.Atoi(st0) return ret
}
func calc(op, xStr, yStr string) string {
x, _ := strconv.Atoi(xStr)
y, _ := strconv.Atoi(yStr)
var ret string
if op == "+" { ret = strconv.Itoa(x + y) }
if op == "-" { ret = strconv.Itoa(x - y) }
if op == "*" { ret = strconv.Itoa(x * y) }
if op == "/" { ret = strconv.Itoa(x / y) }
return ret
}
func isOperator(val string) bool {
return val == "+" || val == "-" || val == "*" || val == "/"
}