Given an expression string array, return the final result of this expression
Notice
The expression contains onlyinteger,+,-,*,/,(,).
Have you met this question in a real interview?
Yes
Example
For the expression2*6-(23+7)/(1+2),
input is
[
"2", "*", "6", "-", "(",
"23", "+", "7", ")", "/",
(", "1", "+", "2", ")"
],
return2
line 23 negate operator
class Solution {
public:
/\*\*
\* @param expression: a vector of strings;
\* @return: an integer
\*/
int evaluateExpression\(vector<string> &expression\) {
// write your code here
stack<int> s1;
stack<string> s2;
for \(string& s : expression\) {
if \(s == "\("\) {
s2.push\(s\);
} else if \(s == "\)"\) {
while \(s2.top\(\) != "\("\) {
calculate\(s1, s2\);
}
s2.pop\(\);
} else {
if \(!IsOperator\(s\)\) {
s1.push\(stoi\(s\)\);
} else {
while \(!s2.empty\(\) && Precedence\(s2.top\(\)\) >= Precedence\(s\)\) {
calculate\(s1, s2\);
}
s2.push\(s\);
}
}
}
while \(!s2.empty\(\)\) {
calculate\(s1, s2\);
}
if \(s1.empty\(\)\) {
return 0;
}
return s1.top\(\);
}
void calculate\(stack<int>& s1, stack<string>& s2\) {
int right = s1.top\(\); s1.pop\(\);
int left = s1.top\(\); s1.pop\(\);
int val = 0;
string op = s2.top\(\);
if \(op == "+"\)
val = left + right;
if \(op == "-"\)
val = left - right;
if \(op == "\*"\)
val = left \* right;
if \(op == "/"\)
val = left / right;
s1.push\(val\);
s2.pop\(\);
}
bool IsOperator\(string& s\) {
return s == "+" \|\| s == "-" \|\| s == "\*" \|\| s == "/";
}
int Precedence\(string& op\) {
if \(op == "+" \|\| op == "-"\) {
return 1;
}
if \(op == "\*" \|\| op == "/"\) {
return 2;
}
return 0;
}
};