表达式计算

思路

一开始直接拿 栈算了, 但是发生了段错误, 原来是可能有多余的括号, QAQ , 有点狗血 , 说实话, 我感觉这个题有点故意恶心人了 , 就是只能用递归写

先看看用栈写的代码, 这个套的yxc的模板写的:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = INT_MAX;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> small_heap;
// #define int long long
stack<int> num;
stack<char> op;
int qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k & 1)
            res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}
void eval()
{
    auto b = num.top();
    num.pop();
    auto a = num.top();
    num.pop();
    auto c = op.top();
    op.pop();
    int x;
    if (c == '+')
        x = a + b;
    else if (c == '-')
        x = a - b;
    else if (c == '*')
        x = a * b;
    else if (c == '/')
        x = a / b;
    else if (c == '^')
        x = qmi(a, b);
    num.push(x);
}
unordered_map<char, int> pr{
    {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};

int32_t main()
{
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++)
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j++] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(')
            op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(')
                eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c])
                eval();
            op.push(c);
        }
    }
    while (op.size())
        eval();
    cout << num.top() << endl;
    return 0;
}

很明显 , 这个代码只适合 合法的表达式计算 , 遇到 ((3 + 4 ) 这种, 就会段错误

然后是用分治的方法解决, 看看雨巨的代码:

#include<bits/stdc++.h>
using namespace std;
string n;
int number(int left, int right){
    //返回字符串n中[left,right]段的数字
    int ans = 0;
    for(int i = left; i <= right; i++)
        ans = ans * 10 + n[i] - '0';
    return ans;
}
int cale(int l, int r){
    int cnt = 0, add = 0, mul = 0, power = 0;
    for(int i = l; i <= r; i++){
        if(n[i] == '(')
            cnt++;
        else if(n[i] == ')')
            cnt--;
        else if(!cnt){  //记录括号外的最后一个符号位置，优先级不同的分开记录
            switch(n[i]){
            case '+':
            case '-':
                add = i;
            case '*':
            case '/':
                mul = i;
            case '^':
                power = i;
            }
        }
    }
    if(cnt > 0 && n[l] == '(')//去掉多余的括号
        return cale(l + 1, r);
    else if(cnt < 0 && n[r] == ')')
        return cale(l, r - 1);
    else if(!cnt && !add && !mul && !power){
        //剩下的式子包在括号里或者只剩下数字，则获取这个数字
        if(n[l] == '(' && n[r] == ')')
            return cale(l + 1, r - 1);
        return number(l, r);
    }
    if(add)
        if(n[add] == '+')
            return cale(l, add-1) + cale(add+1, r);
        else
            return cale(l, add-1) - cale(add+1, r);
    if(mul)
        if(n[mul] == '*')
            return cale(l, mul-1) * cale(mul+1, r);
        else
            return cale(l, mul-1) / cale(mul+1, r);
    if(power)
        return pow(cale(l, power-1), cale(power+1, r));
    return -1;
}
int main(){
    cin>>n;
    cout<<cale(0,n.length()-1)<<endl;
    return 0;
}

这种没考虑第一个是负数的情况, 比如说-1 * 8 ,但是实在写恶心了这道题, 下一道了先