forked from JiauZhang/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0150_evaluate_reverse_polish_notation.cpp
62 lines (57 loc) · 2.21 KB
/
0150_evaluate_reverse_polish_notation.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
* Copyright(c) 2019 Jiau Zhang
* For more information see <https://github.com/JiauZhang/algorithms>
*
* This repo is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation
*
* It is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with THIS repo. If not, see <http://www.gnu.org/licenses/>.
*/
/*
* 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
*
* 解题思路:
* RPN每个运算符对应前边的两个操作数,因此采用栈的方式解决
* 1. 如果取出的数不是运算符,那么就进行入栈操作
* 2. 如果取出的数是运算符,那么就对栈顶的两个数进行操作
* 所以这里涉及到 判断 栈中否至少包含两个操作数
*/
class Solution {
public:
int evalRPN(vector<string> &tokens) {
stack<int> store;
for (auto s: tokens) {
if (s == "+" || s == "-" || s == "*" || s == "/") {
if (store.size()<2)
return false;
int a = store.top(); store.pop();
int b = store.top(); store.pop();
int c;
//需要使用 双引号 而不是 单引号
if (s == "+")
c = a+b;
else if (s == "-")
c = b-a;
else if (s == "*")
c = a*b;
else if (s == "/")
c = b/a;
store.push(c);
} else {
store.push(atoi(s.c_str()));
}
}
return store.top();
}
};