AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 3302. (模拟栈)表达式求值    原题链接    中等

作者: 作者的头像   Avetre ,  2024-11-30 14:24:13 ,  所有人可见 ,  阅读 1


0


#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 10;
// opd(operand)存储操作数 opt(operator)存储操作符
int opd[N], opt[N], top1 = 0, top2 = 0;

bool precede(char top, char curr)
{
    // 如果栈顶操作符优先级高于或等于当前操作符 返回true
    // 为何是高于等于呢?因为减法和除法的操作数有先后顺序性 只是高于的话 会出现1-2+3<->1-(2+3)<->1-5的错误情况
    if ((top == '*' || top == '/') && (curr == '+' || curr == '-'))
        return true;
    if ((top == '+' || top == '-') && (curr == '+' || curr == '-'))
        return true;
    if ((top == '*' || top == '/') && (curr == '*' || curr == '/'))
        return true;
    return false;
}

signed main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        // 处理数字
        if (s[i] >= '0' && s[i] <= '9')
        {
            // 多位数
            int x = 0;
            while (i < s.size() && s[i] >= '0' && s[i] <= '9')
            {
                x = x * 10 + s[i] - '0';
                i++;
            }
            opd[++top1] = x;
            // 因为for循环中有i++ 所以这里要i-- 否则会跳过一个字符
            i--;
        }
        // 处理操作符
        else
        {
            // 左括号:直接入栈
            if (s[i] == '(')
                opt[++top2] = s[i];
            // 右括号:弹出操作符栈中的操作符 并逐次从操作数栈中弹出两个数计算 直到遇到左括号
            else if (s[i] == ')')
            {
                while (opt[top2] != '(')
                {
                    int b = opd[top1--];
                    int a = opd[top1--];
                    if (opt[top2] == '+')
                        opd[++top1] = a + b;
                    else if (opt[top2] == '-')
                        opd[++top1] = a - b;
                    else if (opt[top2] == '*')
                        opd[++top1] = a * b;
                    else if (opt[top2] == '/')
                        opd[++top1] = a / b;
                    // 弹出操作符
                    top2--;
                }
                // 弹出左括号
                top2--;
            }
            // 加减乘除
            else
            {
                // 栈非空 且栈顶操作符不为左括号 且栈顶操作符优先级高于等于当前操作符 则弹出栈顶操作符 并计算
                while (top2 && opt[top2] != '(' && precede(opt[top2], s[i]))
                {
                    int b = opd[top1--];
                    int a = opd[top1--];
                    if (opt[top2] == '+')
                        opd[++top1] = a + b;
                    else if (opt[top2] == '-')
                        opd[++top1] = a - b;
                    else if (opt[top2] == '*')
                        opd[++top1] = a * b;
                    else if (opt[top2] == '/')
                        opd[++top1] = a / b;
                    // 弹出操作符
                    top2--;
                }
                // 当前操作符入栈
                opt[++top2] = s[i];
            }
        }
    }
    // 处理栈中剩余操作符
    while (top2)
    {
        int b = opd[top1--];
        int a = opd[top1--];
        if (opt[top2] == '+')
            opd[++top1] = a + b;
        else if (opt[top2] == '-')
            opd[++top1] = a - b;
        else if (opt[top2] == '*')
            opd[++top1] = a * b;
        else if (opt[top2] == '/')
            opd[++top1] = a / b;
        top2--;
    }
    // 操作数栈中剩下的唯一元素即为结果
    cout << opd[top1] << endl;
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息