Posted on 2012-10-08 17:25
hoshelly 閱讀(1266)
評論(0) 編輯 收藏 引用 所屬分類:
Programming
描述
給一些包含加減號和小括號的表達式，求出該表達式的值。表達式中的數值均為絕對值小于 10 的整數。
輸入
第一行為表達式的個數 n，以下 n 行每行有一個表達式。每個表達式的長度不超過 20 個字符。
輸出
對每個表達式，輸出它的值。
樣例輸入
3
3-(2+3)
-9+8+(2+3)-(-1+4)
0-0
樣例輸出
-2
1
0
//對每種情況都要考慮清楚
#include <cctype>
#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;
int getPrecedence(const char optr) //給各個操作符定義優先級順序，利用map容器
{
map<char, int> precedTable;
precedTable['#'] = 0;
precedTable[')'] = 1;
precedTable['+'] = 2;
precedTable['-'] = 2;
precedTable['*'] = 3;
precedTable['/'] = 3;
precedTable['('] = 10;
return precedTable[optr];
}
int calculate(int a, char optr, int b)
{
switch (optr) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: return 0;
}
}
int evaluate(const string& expr)
{
stack<int> opnd;
stack<char> optr;
char last_ch = '\0'; //每次檢查字符時的前一個字符
for (size_t i = 0; i != expr.size(); ++i) {
const char ch = expr[i];
if (isspace(ch)) { //如果是空格，即跳過
continue;
} else if (isdigit(ch)) { //如果是數字，則壓入操作數棧
opnd.push(ch - '0');
} else {
if ((ch == '-' || ch == '+') && (last_ch == '\0' || last_ch == '(')) //遇到 '+'、'-'，則壓入0進操作數棧
opnd.push(0); //如 7-1，遇'-'則壓入0進棧，，'-'則進操作符棧，遇到下一個數1，計算0-1得-1
if (optr.empty() || ch == '(' || (optr.top() == '(' && ch != ')') || getPrecedence(ch) > getPrecedence(optr.top())) {
optr.push(ch);
}
else
{
while (!optr.empty() && optr.top() != '(' && getPrecedence(ch) <= getPrecedence(optr.top()))
{
int b = opnd.top(); opnd.pop();
int a = opnd.top(); opnd.pop();
opnd.push(calculate(a, optr.top(), b));
optr.pop();
}
if (ch == ')')
optr.pop();
else
optr.push(ch);
}
}
last_ch = ch;
}
while (!optr.empty()) {
int b = opnd.top(); opnd.pop();
int a = opnd.top(); opnd.pop();
opnd.push(calculate(a, optr.top(), b));
optr.pop();
}
int result = opnd.top(); opnd.pop();
return result;
}
int main()
{
int n;
cin >> n;
while (n-- > 0) {
string expr;
cin>>expr;
cout << evaluate(expr) << endl;
}
return 0;
}