Posted on 2012-10-08 17:25
hoshelly 阅读(1228)
评论(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;
}