题解 | #表达式求值#

表达式求值

http://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d

思路:

  1. 将表达式转为逆波兰式;
  2. 计算逆波兰式的值。
    PS:默认表达式中不含空格。
#include <iostream>
#include <string>
#include <stack>
using namespace std;

// 通过一个单调栈(存储操作符)将表达式转为逆波兰式
string trans(string exp) {
    stack<char> opt_stk;
    int idx = 0, len = exp.length();
    string ans;
    char num_sign = '#';
    while (idx < len) {
        switch (exp[idx]) {
            case '(':
                opt_stk.push('(');
                idx++;
                break;
            case ')':
                while (opt_stk.top() != '(') {
                    ans += opt_stk.top();
                    opt_stk.pop();
                }
                opt_stk.pop();
                idx++;
                break;
            case '+':
            case '-':
                // 以下两种情况将负号视作符号位,不将其入栈
                // 1. 负号在第一位
                // 2. 负号前一位字符不是数字,也不是反括号
                if (exp[idx] == '-' && (idx == 0 || (idx > 0 && exp[idx-1] != ')' && !isdigit(exp[idx-1])))) {
                    num_sign = '@';
                    idx++;    
                } else {
                    while (!opt_stk.empty() && opt_stk.top() != '(') {
                    ans += opt_stk.top();
                    opt_stk.pop();
                    }
                    opt_stk.push(exp[idx++]);
                }
                break;
            case '*':
            case '/':
                while (!opt_stk.empty()) {
                    char c = opt_stk.top();
                    if (c == '*' || c == '/') {
                        ans += c;
                        opt_stk.pop();
                    } else 
                        break;
                }
                opt_stk.push(exp[idx++]);
                break;
            default:
                while (idx < len && exp[idx] <= '9' && exp[idx] >= '0') 
                    ans += exp[idx++];
                ans += num_sign;
                if (num_sign == '@') num_sign = '#';
        }
    }
    while (!opt_stk.empty()) {
        ans += opt_stk.top();
        opt_stk.pop();
    }
    return ans;
}

// 也只用一个栈,栈中存放的是操作数
double compute_value(string exp) {
    stack<double> stk;
    int idx = 0, len = exp.length();
    while (idx < len) {
        char c = exp[idx];
        if (c == '+') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(a + b);
        } else if (c == '-') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(b - a);
        } else if (c == '*') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(a * b);
        } else if (c == '/') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(b / a);
        } else {
            double num = 0;
            while (exp[idx] <= '9' && exp[idx] >= '0') 
                num = num * 10 + exp[idx++] - '0';
            if (exp[idx] == '@') num = -num;
            stk.push(num);
        }
        idx++;
    }
    return stk.top();
}

int main() {
    string exp;
    cin >> exp;
//     cout << trans(exp) << endl;
    cout << compute_value(trans(exp));

    return 0;
}
全部评论

相关推荐

工作基本定了,比较满意。这深度学习真是难搞啊,论文看不懂,代码看不懂,不会改,创新点???&nbsp;还有一个月中期,怎么搞,已经抑郁了,没有小论文要求,我真是非常幸运了,不然就我这科研能力…………&nbsp;感觉自己对自己失去信心,无时无刻不在否定自己取得一些成绩都是运气好罢了,真的能顺利毕业吗?严重内耗、无力感爆棚啊…………
AI牛可乐:哎呀,听起来你最近压力好大呀,毕业论文和工作的双重压力一定让你感觉像是背了两座山呢。深度学习确实挺复杂的,就像是要在一片迷雾中找到出路一样。但是,你已经很棒了,工作都定好了,这是很大的成就呢! 论文的事情,别太担心。每个人都有看不懂代码和论文的时候,这是正常的。至于创新点嘛,有时候灵感就像小猫一样,需要一点一点地哄出来的。你可以先试试把你看过的资料整理一下,说不定就能找到新的思路呢。 中期答辩前,你可以列个计划,一步一步来,把大问题分解成小问题,一点一点克服。记得,你不是一个人在战斗,你的导师、同学都是你的战友哦。 至于信心嘛,别否定自己,每个人都会有低谷的时候。你已经取得的成绩,都是你实力的体现。毕业不是问题,只要你不放弃,就一定能顺利走过去的。加油哦,我相信你可以的! 对了,如果你愿意的话,可以点击我的头像,我们私信聊,也许我能帮你出出主意,或者就是简单地聊聊天,分散一下你的注意力也好呀。🐮💪🌟
点赞 评论 收藏
分享
球球别再泡了:坏,我单9要了14
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务