-
Notifications
You must be signed in to change notification settings - Fork 0
/
Evaluate_Reverse_Polish_Notation.cpp
73 lines (73 loc) · 2.34 KB
/
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
63
64
65
66
67
68
69
70
71
72
73
//////////////////////////////////////////////////////
// Project: MyLeetCode
//
// Author: YanShicong
// Date: 2014/11/25
//////////////////////////////////////////////////////
/*--------------------------------------------------------------------------------------------------------------
* Evaluate the value of an arithmetic expression in Reverse Polish Notation.
* http://en.wikipedia.org/wiki/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
//--------------------------------------------------------------------------------------------------------------*/
#include "../include/include.h"
// 时间复杂度O(n),空间复杂度O(logn)。
class Solution {
public:
int evalRPN(vector<string> &tokens) {
if (tokens.empty()) return 0;
stack<string> cal_stack; // 栈中存字符串
#if __cplusplus < 201103L
for (auto it = tokens.begin(); it != tokens.end(); ++it)
{
string token = *it;
#else
for (auto token : tokens)
{
#endif
if (!is_operator(token))
{
cal_stack.push(token);
}else
{
int y = stoi(cal_stack.top()); // stoi
cal_stack.pop();
int x = stoi(cal_stack.top());
cal_stack.pop();
if (token[0] == '+') { x += y;} // 用自增操作,少一个变量
else if (token[0] == '-') { x -= y;}
else if (token[0] == '*') { x *= y;}
else if (token[0] == '/') { x /= y;}
cal_stack.push(to_string((long double)x)); // to_string
}
}
return stoi(cal_stack.top());
}
private:
bool is_operator(const string& op)
{
return op.size() == 1 && string("+-*/").find(op) != string::npos; // 这种写法很好,判断某string在不在若干选择之中
}
};
//--------------------------------------------------------------------------------------------------------------
TEST_CASE("Evaluate_Reverse_Polish_Notation", "[Stacks]"){
Solution sln;
vector<string> tokens;
SECTION("Empty Input"){
REQUIRE(sln.evalRPN(tokens) == 0);
}
SECTION("Normal Input1"){
string temp[5] = {"2", "1", "+", "3", "*"};
tokens.assign(temp, temp+5);
REQUIRE(sln.evalRPN(tokens) == 9);
}
SECTION("Normal Input2"){
string temp[5] = {"4", "13", "5", "/", "+"};
tokens.assign(temp, temp+5);
REQUIRE(sln.evalRPN(tokens) == 6);
}
}