AcWing 151. 表达式计算4

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 151. 表达式计算4 原题链接简单

作者：

秦淮岸灯火阑珊 , 2019-01-30 09:47:21 , 所有人可见 , 阅读 3826

15

5

题目描述

给出一个表达式,其中运算符仅包含

+,-,*,/,^

（加减乘整除乘方）要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现大于或等于$2^{31}$的答案。

数据可能会出现负数情况。

输入格式
输入仅一行，即为表达式。

输出格式
输出仅一行，既为表达式算出的结果。

样例

输入样例：
(2+2)^(1+1)
输出样例：
16

模拟+栈

其实就是不断的模拟四则运算,不过要记住,括号的运算级别是最低的,而不是最高的,和普通运算不一样,因为我们是在通过栈去模拟,一旦遇到括号,我们就要将括号外面的值都算完,所以括号等级要最低,否则将会出错,具体思想可见代码模拟.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=110;
char s[N];
stack<int> q1,q2;
int power(int a,int b)//快速幂求值
{
    int ans=1;
    while(b)
    {
        if (b&1)
            ans=ans*a;
        a*=a;
        b>>=1;
    }
    return ans;
}
int check(char c) //check算出等级,记住要+,-虽然是同等级,但是我们一样还是设为不同等级,因为不然不好计算值,但是排序中是同等级的.
{
    if(c=='(') 
        return -2;
    if(c==')') 
        return -1;
    if(c=='^') 
        return 5;
    if(c=='*') 
        return 4;
    if(c=='/') 
        return 3;
    if(c=='+') 
        return 2;
    if(c=='-') 
        return 1;
    return 0;
}
int calc(int x) 
{
    int a,b;
    b=q2.top();
    q2.pop();
    if(q2.empty() && x==1) 
        a=0;
    else 
    {
        a=q2.top();
        q2.pop();
    }
    if(x==2) 
        return a+b;
    if(x==1) 
        return a-b;
    if(x==4) 
        return a*b;
    if(x==3) 
        return a/b;
    if(x==5) 
    {
        int ans=power(a,b);
        return ans;
    }
}
bool cmp(int x,int y) 
{
    if(x&1) //+,-同等级 *,/同等级,(,)同等级
        x++;
    if(y&1) //+,-同等级 *,/同等级,(,)同等级 这里是将等级一致
        y++;
    return x>=y;
}
int main() 
{
    scanf("%s",s+1);
    int len=strlen(s+1),x=0,y,z;
    s[0]='(';
    s[++len]=')';
    fir(i,0,len)
    {
        y=check(s[i]);
        if(!y) //数字
        {
            x=x*10+s[i]-'0';
            continue;
        }
        if(!check(s[i-1]) && i) //符号
        {
            q2.push(x);
            x=0;
        }
        if(y==-1) //是右括号,说明开始括号内计算.
        {
            z=q1.top();q1.pop();
            while(z!=-2) //如果不是左括号,不断处理内部的运算
            {
                q2.push(calc(z));
                z=q1.top();
                q1.pop();
            }
            continue;
        }
        if(y!=-2) //不是左括号
        {
            while(!q1.empty() && cmp(q1.top(),y))//不断地运算,也就是将运算栈中的所有符号,开始运算
            {
                z=q1.top();
                q1.pop();
                q2.push(calc(z));
            }
        }
        q1.push(y);
    }
    printf("%d\n",q2.top());
    return 0;
}

16 评论

acwing_794723 6天前

ntt

times_lover 2023-09-18 17:12

有一个想法，与其说是括号优先级别最低，不如说右括号优先级别最低，左括号优先级别最高。
因为这里所谓的优先级别，实质上就是运算符的出栈顺序，如果比前面的运算符优先级高就不出栈，相等或低就出栈；右括号出现时一定要直接出栈，所以优先级最低；左括号出现一定不出栈，所以优先级最高。

SWC 8个月前

(+怎么办？你括号后面不跟上符号的吗？

Hsy_Tony 2022-01-26 13:59

+-应该属于同一等级的吧

heiyou 2020-09-05 17:42

啊这让我想到了编译原理，搞一个语法树来算

whsstory 2019-08-22 12:48

hack数据：(-1)))
(不要觉得这个数据不合法，此题有((((-1)的数据)

秦淮岸灯火阑珊 2019-08-22 17:58

强啊，感谢您的贡献。

扶摇直上九万里 2019-12-30 20:25

但是这个数据表达确实不合法呀

YimingLi 2020-12-18 12:31 回复了扶摇直上九万里的评论

这个数据现在测试数据里面有了，秦佬这份代码直接 Segmentation Fault

YimingLi 2020-12-18 12:47 回复了 YimingLi 的评论

我的AC代码：

/*
中缀表达式求值，有两种做法：
1. 转换为后缀表达式再求值：O(N)
2. 递归法求值：O(N^2)
这里使用方法 1
注意这个题目还要处理负数的符号位的情况，例如 -3+1
- 到底是负号还是减号?
特例：
((((((-1)
(-1)))
(1+2)^((-1+1))
*/
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

vector<int> nums;
vector<char> ops;
string s;

// 优先级
int grade(char op) {
    switch (op) {
        case '(':
            return 1;
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;
        case '^':
            return 4;
    }
    return 0;
}
// 处理后缀表达式中的一个运算符
void calc(char op) {
    // 从栈顶取出两个数
    int y = nums.back();
    nums.pop_back();
    int x = 0;
    // 如果出现负号的情况：
    // 1. 可能没有多的操作数了，前一个操作数当做 0 看待
    // 2. 可能前面是左括号 (，需要先把这个负数计算出来（0 - y = -y）
    if (nums.size() && !(op == '-' && ops.size() && ops.back() == '(')) {
        x = nums.back();
        nums.pop_back();
    }
    int z;
    switch (op) {
        case '+':
            z = x + y;
            break;
        case '-':
            z = x - y;
            break;
        case '*':
            z = x * y;
            break;
        case '/':
            z = x / y;
            break;
        case '^':
            z = pow(x, y);
    }
    // cout << x << op << y << " = " << z << endl;
    // 把运算结果放回栈中
    nums.push_back(z);
}
int main() {
    cin >> s;
    int val = 0;
    for (int i = 0; i < s.length(); i++) {
        // 多位数， 并且表达式是使用字符串逐字符存储的，我们只需要稍加判断，把连续的一段数字看成一个数即可。
        if (s[i] >= '0' && s[i] <= '9') {
            val = val * 10 + s[i] - '0';
            if (s[i + 1] >= '0' && s[i + 1] <= '9') continue;
            // 后缀表达式的一个数，直接入栈
            nums.push_back(val);
            val = 0;
        }
        // 左括号：直接入栈
        else if (s[i] == '(')
            ops.push_back('(');
        // 右括号：一直出栈直到遇见左括号
        else if (s[i] == ')') {
            while (ops.size() && ops.back() != '(') {
                // 出栈一个符号就计算一下
                char op = ops.back();
                ops.pop_back();
                calc(op);
            }
            // 左括号出栈（如果有的话）
            if (ops.size()) ops.pop_back();
        }
        // 运算符：只要栈顶符号的优先级不低于新符号，就不断取出栈顶并输出，最后把新符号进栈，其实只在这里使用了优先级的比较
        else {
            while (ops.size() && grade(ops.back()) >= grade(s[i])) {
                char op = ops.back();
                ops.pop_back();
                calc(op);
            }
            ops.push_back(s[i]);
        }
    }
    // 剩下符号再计算一下
    while (ops.size() && nums.size() >= 2) {
        char op = ops.back();
        ops.pop_back();
        calc(op);
    }
    // 后缀表达式栈中最后剩下的数就是答案
    cout << nums.front() << endl;
    return 0;
}