题解 | #表达式计算4#

我参考了不少已有的解析，所以说我写的代码还是老掉牙的递归，对于CPP模拟计算式而言，这确实是最好的办法了

思路各位大神的题解已经说的很清楚了，我在这里主要是对于“开头负数是否可以处理”发表我的看法——可以不单独显示处理！

我们之所以可以处理负数，主要归功于(l > r)时返回0，这一个看似无聊的常规操作却能够奇妙的处理符号问题。我的代码同级是以右边的为优先，比如例子3+-5，先拿到-，之后分割为3+与5，5不用管，对于左边的3+，+右边pos+1会大于原本的r以至于返回0，也就是3+0-5，可以正常操作

我发现很多人的代码里，pos初始化都是-1，实际上可以改为LLONG_MIN

我们有举一个例子：-5 + 3，先拿到3，分为3与-5，我们看-5，右边拿到5，左边的符号右边会变为pos-1也就是-1，如果pos初始化为-1那确实是无计可施，不过变为LLONG_MIN，对于（0，-1），r会小于l，所以说会返回0，也就是0-5+3！

当然这也只是我的思路，如果有错也希望各位大佬指出

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

string str;

int num(int l,int r)
{
    int ans = 0;
    
    for(int u = l;u <= r;u++)
    {
        ans = ans * 10 + (str[u] - '0');
    }
    
    return ans;
}
//经典转化，这里不使用string的原因只是因为我们实际上没有切割字符串，切割的实际上只有区间

int opp(char s)
{
    if(s == '+' || s == '-')
    {
        return 1;
    }
    else if(s == '*' || s == '/')
    {
        return 2;
    }
    else if(s == '^')
    {
        return 3;
    }
    else
    {
        return 0;
    }
}

int solve(int l,int r)
{
    if(l > r)
    {
        return 0;
    }
    
    int pos1 = LLONG_MIN,pos2 = LLONG_MIN,pos3 = LLONG_MIN;
    
    int cnt = 0;
    
    for(int o = l;o <= r;o++)
    {
        if(str[o] == '(')
        {
            cnt++;
        }
        else if(str[o] == ')')
        {
            cnt--;
        }
        
        if(cnt == 0)//要么是左右全对应上了，要么是压根没有。如果到了最后还不为0，我们有讨论方式
        {
            if(opp(str[o]) == 1)
            {
                pos1 = o;
            }
            else if(opp(str[o]) == 2)
            {
                pos2 = o;
            }
            else if(opp(str[o]) == 3)
            {
                pos3 = o;
            }
        }
    }
    
    if(pos1 == LLONG_MIN && pos2 == LLONG_MIN && pos3 == LLONG_MIN)
    {
        //除开只有括号的情况，还有可能是全程记录时cnt都没有正确对应上过
        //我们需要在这一步进行分类讨论
        
        if(cnt > 0 && str[l] == '(')
        {
            return solve(l + 1,r);
        }
        else if(cnt < 0 && str[r] == ')')
        {
            return solve(l,r - 1);
        }
        else if(cnt == 0 && str[r] == ')' && str[l] == '(')
        {
            return solve(l + 1,r - 1);
            //理想情况下（没有多余符号）的溢出条件
        }
        else
        {
            return num(l,r);
        }
        
        //核心是由于括号的优先级最高，所以说括号内的我们先不要去分割，不去记录他的pos，等到只有他时再去处理
        
    }
    else
    {
        if(pos1 > LLONG_MIN)
        {
            if(str[pos1] == '+')
            {
                return solve(l,pos1 - 1) + solve(pos1 + 1,r);
            }
            else
            {
                return solve(l,pos1 - 1) - solve(pos1 + 1,r);
            }
        }
        else if(pos2 > LLONG_MIN)
        {
            if(str[pos2] == '*')
            {
                return solve(l,pos2 - 1) * solve(pos2 + 1,r);
            }
            else
            {
                return solve(l,pos2 - 1) / solve(pos2 + 1,r);
            }            
        }
        else
        {
            return pow(solve(l,pos3 - 1),solve(pos3 + 1,r));
        }
    }
}

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin>>str;
    
    cout<<solve(0,str.length() - 1)<<endl;
    
    return 0;
}