AcWing 3302. 表达式求值

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 3302. 表达式求值原题链接简单

作者：

acm_wf , 2021-03-13 16:10:13 , 所有人可见 , 阅读 4657

40

11

搬砖，学习y总的代码，顺带打上注释

基本思路：
针对这一问题，我们运算的时候是要考虑运算符优先级问题的，那么就得把优先级高的数据先处理，很自然地就选择了栈来倒序。
我们人在做这样计算题的时候，往往也是先去寻找乘除先计算，写出计算结果，最后再看加减运算，那么自然乘除比加减高上一级，在此之上是括号
在这个思路上，去看代码就更为容易看懂了

#include<iostream>
#include<unordered_map>
#include<stack>

using namespace std;

//存储运算数 运算符
stack<int> num;
stack<char> op;
//建立映射来判断运算优先级
unordered_map<char, int> cmp = {
    {'+', 1}, {'-', 1} , {'*', 2}, {'/', 2}
};
//模拟一次算术操作
void eval(void){
    int b = num.top();  num.pop();
    int a = num.top();  num.pop();
    char opr = op.top();    op.pop();

    int x;
    if(opr == '+')  x = a + b;
    else if(opr == '-') x = a - b;
    else if(opr == '*') x= a * b;
    else    x = a / b;
    num.push(x);
}

int main(){
    string str;
    cin >> str;

    for(int i = 0; i < str.size(); i++){
        char c = str[i];
        //读入运算数
        if(isdigit(c)){
            int j = i, x = 0;
            while( j < str.size() && isdigit(str[j])){
                //j++ 迭代不能忘 
                x = x *  10 + str[j ++] - '0';
            }
            num.push(x);
            //由于每轮循环有i++,我们需要倒指向最后一个数字
            i = j - 1;
        }else if( c == '(' ){
            //标记一下，括号内数据
            op.push(c);
        }else if( c == ')' ){
            //括号的优先级，先算括号
            while( op.size() && op.top() != '(' )   eval();
            //左括号可以弹出
            op.pop();
        }else{
            //得先把乘除法算了再算加减
            //这里必须得带等于号 我们这题都是正整数计算
            // 0 - 5 + 3 
            //如果不算，上式会被错误计算成 -8
            while( op.size() && cmp[op.top()] >= cmp[c])    eval();
            //压入新运算符
            op.push(c);
        }
    }
    //清理低优先级操作
    while(op.size())    eval();
    cout << num.top() << endl;
    return 0;
}

49 评论

Critic 2021-12-23 15:36

顶一下，写得很好。
ps：评论能别建“基站”吗，很影响其他人的观感。

蜡笔小辛 11个月前

#秒啊

Shreyansh_M 2022-11-05 21:28

秒啊📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊

L-China 2022-12-12 12:29

大佬，你这个基站咋打上去的？

令人_4 9个月前回复了 L-China 的评论

📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊

xmvim 2021-03-21 10:10

while( op.size() && cmp[op.top()] >= cmp[c]) eval(); 请问一下，这里为啥用 while 呢，我用 if 出错后没举出来例子…

xmvim 2021-03-21 10:23

啊啊啊啊，我傻了。借用您的例子稍作修改， 0-5*3+1，即能说明问题，手动模拟一下即可。但是其实这个 while() 其实最多也只会执行两次，我将其改为两个 if ( op.size() && cmp[op.top()] >= cmp[c]) eval(); 也 AC 了。这下终于通了.......吧哈哈

acm_wf 2021-03-21 15:33 回复了 xmvim 的评论

hh式子可以很长的！好棒！

Eric_Cao 2021-03-22 11:11 回复了 xmvim 的评论

大佬赞！我也遇到了这个问题，出错的那个测试用例一大串直接看晕了hhh

苦练dp 1个月前

一只big龙猫 6个月前

📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊
📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊
📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊
📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊
📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊
📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊