简单表达式求值。数字为个位数，可能为负数，运算符包括 +, -, *, /, (, ) 这几种

evaluate_expression.cc

/*
 * 表达式求值（http://www.bianchengla.com/course/ds/practise/problem?id=1322）
 *
 *    时间限制：1000 ms    内存限制：65536 KB
 *
 * 描述
 *
 *    给一些包含加减号和小括号的表达式，求出该表达式的值。表达式中的数值均为
 *    绝对值小于 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<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 {
            // In case of a positive sign (+) or nagative sign (-),
            // push a zero on to the operand stack
            if ((ch == '-'  || ch == '+') && (last_ch == '\0' || last_ch == '('))
                opnd.push(0);
            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()
{
    unsigned n;
    cin >> n;
    cin.get();
    while (n-- > 0) {
        string expr;
        getline(cin, expr);
        cout << evaluate(expr) << endl;
    }
    return 0;
}

input.txt

13
3-(2+3)
-9+8+(2+3)-(-1+4)
0-0
1+2*3*4
1+2*3*4-6
1+2*3*4-6/2
+9+6
(1+2)*3*4-5
-9
(5)
(-9)
(-6+9)
(-2)*(-6+9)

output.txt

-2
1
0
25
19
22
15
31
-9
5
-9
3
-6