forked from kamyu104/LintCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
expression-evaluation.cpp
158 lines (150 loc) · 4.78 KB
/
expression-evaluation.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// Time: O(n)
// Space: O(n)
class Solution {
public:
/**
* @param expression: a vector of strings;
* @return: an integer
*/
int evaluateExpression(vector<string> &expression) {
stack<int> operands;
stack<string> operators;
if (expression.empty()) {
return 0;
}
for (int i = expression.size() - 1; i >= 0; --i) {
if (isdigit(expression[i][0])) {
operands.emplace(stoi(expression[i]));
} else if (expression[i] == ")" || expression[i] == "*" ||
expression[i] == "/") {
operators.emplace(expression[i]);
} else if (expression[i] == "+" || expression[i] == "-") {
while (!operators.empty() && (operators.top() == "*" ||
operators.top() == "/")) {
compute(operands, operators);
}
operators.emplace(expression[i]);
} else if (expression[i] == "(") {
// operators at least one element, i.e. ")".
while (operators.top() != ")") {
compute(operands, operators);
}
operators.pop();
}
}
while (!operators.empty()) {
compute(operands, operators);
}
return operands.top();
}
void compute(stack<int>& operands, stack<string>& operators) {
const int left = operands.top();
operands.pop();
const int right = operands.top();
operands.pop();
const string op = operators.top();
operators.pop();
if (op == "+") {
operands.emplace(left + right);
} else if (op == "-") {
operands.emplace(left - right);
} else if (op == "*") {
operands.emplace(left * right);
} else if (op == "/") {
operands.emplace(left / right);
}
}
};
// Time: O(n)
// Space: O(n)
class Solution2 {
public:
/**
* @param expression: a vector of strings;
* @return: an integer
*/
int evaluateExpression(vector<string> &expression) {
if (expression.empty()) {
return 0;
}
vector<string> postfix;
infixToPostfix(expression, postfix);
return evaluatePostfixExpression(postfix);
}
// Evaluate Postfix Expression.
int evaluatePostfixExpression(const vector<string> &postfix) {
if (postfix.empty()) {
return 0;
}
stack<string> s;
for (const auto& tok : postfix) {
if (!is_operator(tok)) {
s.emplace(tok);
} else {
int y = stoi(s.top());
s.pop();
int x = stoi(s.top());
s.pop();
if (tok[0] == '+') {
x += y;
} else if (tok[0] == '-') {
x -= y;
} else if (tok[0] == '*') {
x *= y;
} else {
x /= y;
}
s.emplace(to_string(x));
}
}
return stoi(s.top());
}
bool is_operator(const string &op) {
return op.length() == 1 && string("+-*/").find(op) != string::npos;
}
// Convert Infix to Postfix Expression.
void infixToPostfix(vector<string>& infix, vector<string>& postfix) {
stack<string> s;
for (auto tok : infix) {
// Any number would be pushed into stack.
if (atoi(tok.c_str())) {
postfix.emplace_back(tok);
} else if (tok == "(") {
s.emplace(tok);
} else if (tok == ")") {
// Meet ")", then pop until "(".
while (!s.empty()) {
tok = s.top();
s.pop();
if (tok == "(") {
break;
}
postfix.emplace_back(tok);
}
} else {
// Order of tokens in stack should be like "(-*",
// The token will be added in an strictly increasing precedence order.
while (!s.empty() && precedence(tok) <= precedence(s.top())) {
postfix.emplace_back(s.top());
s.pop();
}
s.emplace(tok);
}
}
// Pop the remaining token and add them to the postfix.
while (!s.empty()) {
postfix.emplace_back(s.top());
s.pop();
}
}
int precedence(string x) {
if (x == "(") { // The least precedence.
return 0;
} else if (x == "+" || x == "-") {
return 1;
} else if (x == "*" || x == "/") {
return 2;
}
return 3;
}
};