NC50999 表达式计算4

题目：给你一个含^(乘方)与多余的括号的表达式，输出结果
思路：分治
利用递归将每个括号与符号左右拆分成一个个小式子再在计算中合并到一起
具体看代码实现（参考了较多雨巨的代码）
代码：

#include <iostream>
#include <string>
#include <math.h>
using namespace std;
string s;
int num(int l,int r)//把字符串转换成数字
{
    int ans=0;
    for(int i=l; i<=r; i++)
    {
        ans*=10;
        ans+=s[i]-'0';
    }
    return ans;
}
int solve(int l,int r)
{
    int pos1=-1,pos2=-1,pos3=-1;//pos1记录+-，pos2记录*/，pos3记录^
    int cnt=0;//记录括号
    if(l>r)return 0;
    if(l==r)return s[l]-'0';
    for(int i=l; i<=r; i++)
    {
        if(s[i]=='(')cnt++;
        if(s[i]==')')cnt--;
        if(cnt==0)//当cnt==0时说明目前没有括号了
        {
            if(s[i]=='+'||s[i]=='-')pos1=i;
            if(s[i]=='*'||s[i]=='/')pos2=i;
            if(s[i]=='^')pos3=i;
        }
    }
    if(pos1==-1&&pos2==-1&&pos3==-1)//如果一直没记录到运算符说明要不数与运算符都在括号里面，要不就是只有数字没有括号
    {
        if(cnt>0&&s[l]=='(')return solve(l+1,r);//如果是开头((多出来的直接去掉
        else if(cnt<0&&s[r]==')')return solve(l,r-1);//同理结尾多出来的直接去掉
        else if(cnt==0&&s[l]=='('&&s[r]==')')return solve(l+1,r-1);//还有（1+2+3）这种情况的也直接去掉括号
        else return num(l,r);//不然就说明全部都是数字，转化成数字
    }
    if(pos1>=0)//操作运算符了
    {
        if(s[pos1]=='+')return solve(l,pos1-1)+solve(pos1+1,r);//左右拆分
        else return solve(l,pos1-1)-solve(pos1+1,r);
    }
    else if(pos2>=0)
        if(s[pos2]=='*')return solve(l,pos2-1)*solve(pos2+1,r);
        else return solve(l,pos2-1)/solve(pos2+1,r);
    else if(pos3>=0)
        return pow(solve(l,pos3-1),solve(pos3+1,r));
    else return 0;//这里不加return 0会编译报错说没出口
}
int main()
{
    cin>>s;
    cout<<solve(0,s.size()-1);
    return 0;
}