天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

简单表达式求值

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理