問題
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
例子
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
分析
使用棧來保存臨時的計算結(jié)果和符號。
遍歷字符串，根據(jù)當(dāng)前字符的不同破喻，分別進行如下處理：
- 數(shù)字位：即當(dāng)前字符為'0'-'9'這十個數(shù)字之間煌张，用該字符更新當(dāng)前數(shù)字的大小在张；
- '+'或'-'：說明數(shù)字已經(jīng)結(jié)束，把當(dāng)前的數(shù)字加或減到當(dāng)前結(jié)果上，更新符號夷磕，并把當(dāng)前數(shù)字置為0；
- '('：把當(dāng)前結(jié)果和符號壓入棧中仔沿，并把當(dāng)前結(jié)果置為0坐桩；
- ')'：說明數(shù)字已經(jīng)結(jié)束，把當(dāng)前的數(shù)字加或減到當(dāng)前結(jié)果上于未，并讓以前的符號和符號和結(jié)果出棧撕攒，把當(dāng)前的結(jié)果加或減到以前結(jié)果上陡鹃。把當(dāng)前數(shù)字置為0。
要點
遇到'('時抖坪，將當(dāng)前結(jié)果和符號入棧萍鲸；遇到')'時，讓以前的符號和結(jié)果出棧擦俐。
時間復(fù)雜度
O(n)
空間復(fù)雜度
O(1)
代碼
class Solution {
public:
int calculate(string s) {
stack<int> es;
int res = 0, sign = 1, num = 0;
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
num = num * 10 + c - '0';
}
else if (c == '+' || c == '-') {
res += sign * num;
sign = c == '+' ? 1 : -1;
num = 0;
}
else if (c == '(') {
es.push(res);
es.push(sign);
res = 0;
sign = 1;
}
else if (c == ')') {
res += sign * num;
res *= es.top(); es.pop();
res += es.top(); es.pop();
num = 0;
}
}
// 處理沒有括號的情況脊阴，例如1 1-100
if (num != 0) res += sign * num;
return res;
}
};
