栈的应用之表达式

（1）递归计算中缀表达式,时间复杂度O(n^2)
目标，求解中缀表达式S[1~N]的值
子问题:求解中缀表达式S[L~R]的值，
1.在L~R中没有被任何括号包含的运算符
（1）若存在加减号，选其中最后一个，分成左右两半递归，结果相加减,返回
(2)如果存在乘除号，选其中最后一个，分成左右两半递归，结果相乘除，返回
2.若不存在没有被任何括号包含的运算符.
(1)首尾字符是括号，递归求解S[l+1~r-1]把结果返回
(2)否则，说明区间SL~R]是一个数，直接返回数值

int calc(int l, int r) {
    // 寻找未被任何括号包含的最后一个加减号
    for (int i = r, j = 0; i >= l; i--) {
        if (s[i] == '(') j++;
        if (s[i] == ')') j--;
        if (j == 0 && s[i] == '+') return calc(l, i - 1) + calc(i + 1, r);
        if (j == 0 && s[i] == '-') return calc(l, i - 1) - calc(i + 1, r);
    }
    // 寻找未被任何括号包含的最后一个乘除号
    for (int i = r, j = 0; i >= l; i--) {
        if (s[i] == '(') j++;
        if (s[i] == ')') j--;
        if (j == 0 && s[i] == '*') return calc(l, i - 1) * calc(i + 1, r);
        if (j == 0 && s[i] == '/') return calc(l, i - 1) / calc(i + 1, r);
    }
    // 首尾是括号
    if (s[l] == '('&&s[r] == ')') return calc(l + 1, r - 1);
    // 是一个数
    int ans = 0;
    for (int i = l; i <= r; i++) ans = ans * 10 + s[i] - '0';
    return ans;
}

表达式求值2

j将中缀表达式转化为后缀表达式，求值

#include<bits/stdc++.h>
#include<stack>
using namespace std;
stack<double>nums;
stack<char>ops;
void cal()
{
    double a=nums.top();nums.pop();
    double b=nums.top();nums.pop();
    char c=ops.top();ops.pop();
    double d;
    if(c=='+')d=a+b;
    else if(c=='-')d=b-a;
    else if(c=='*')d=b*a;
    else if(c=='/')d=b/a;
    else
    {
        d=1;
        while(a--)d=d*b;
    }
    nums.push(d);
}
int main()
{
    string str;

    cin>>str;

    string left;

    for(int i=0;i<str.size();i++)left+='(';
    str=left+str+')';
    for(int i=0;i<str.size();i++)
    {
        if(str[i]>='0'&&str[i]<='9')
        {
            int j=i;
            double r=0;
            while(str[j]>='0'&&str[j]<='9')
            {
                r=r*10+str[j]-'0';
                j++;
            }
            i=j-1;
            if(str[j]=='.')//处理小数
            {
                int k=0,l=j+1,s=0;
                while(str[l]>='0'&&str[l]<='9')
                {
                    k++;
                    s=s*10+str[l]-'0';
                    l++;
                }
                r+=pow(0.1,k)*s;
                i=l-1;
            }


            nums.push(r);
        }
        else 
        {
            char c=str[i];
             if(c=='(')ops.push(c);
             else if(c=='+'||c=='-')
             {
                 if(c=='-'&&!(str[i-1]>='0'&&str[i-1]<='9'||str[i-1]==')'))
                 {
                     int j=i+1,r=0;
                   while(str[j]>='0'&&str[j]<='9')
                  {
                   r=r*10+str[j]-'0';
                   j++;
                  }
                   i=j-1;
                  nums.push(-r);
                 }
                 else
                 {
                     if(ops.top()!='(')cal();
                     ops.push(c);
                 }
             }
             else if(c=='*'||c=='/')
             {
                 while(ops.top()=='*'||ops.top()=='/'||ops.top()=='^')cal();
                 ops.push(c);
             }
             else if(c=='^')
             {
                 while(ops.top()=='^')cal();
                 ops.push(c);
             }
             else if(c==')')
             {
                 while(ops.top()!='(')cal();
                 ops.pop();
             }
             else cout<<"invalid operator!"<<endl;
        }
    }
    cout<<nums.top();
    return 0;
}