题目描述

本文仅作为记录，具体参考这位大佬的博客：
https://www.cnblogs.com/Tyouchie/p/11570638.html

中缀、后缀表达式的计算

可以有 +、-、*、/、^、(、);

可以有负数
可以有多余括号
可以有多位数

算法1

(暴力枚举) $O(n^2)$

后缀表达式的计算

时间复杂度

参考文献

C++ 代码

void cal() {//计算表达式的值 按照后缀表达式的方式
    int num1,num2,num3;
    num1=num.top(); num.pop();
    num2=num.top(); num.pop();
    char op=ops.top(); ops.pop(); 
    if(op=='+') num3=num2+num1;
    else if (op=='-') num3=num2-num1;
    else if (op=='*') num3=num2*num1;
    else if (op=='/') num3=num2/num1;
    else num3=mul(num2,num1);
    num.push(num3);//计算结果压入栈中
}

算法2

(暴力枚举) $O(n^2)$

中缀转后缀

C++ 代码

    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,t=0;
            while(str[j]>='0'&&str[j]<='9') {
                t=t*10+str[j]-'0';
                j++;
            }
            num.push(t);//处理多位数字的情况 题目并没有保证是10以内的数字
            i=j-1;
        }
        else {
            char c=str[i];
            if(c=='(') ops.push(c);//左括号 直接入栈 
            else if(c=='+'||c=='-') {
                if(c=='-'&&i&&!(str[i-1]>='0'&&str[i-1]<='9')&&str[i-1]!=')') {//处理负数的情况 将减去一个数 改成+负数 
                    int j=i+1,t=0;
                    while(str[j]>='0'&&str[j]<='9') {
                        t=t*10+str[j]-'0';
                        j++;
                    }
                    num.push(-t);
                    i=j-1;
                }
                else {
                    while(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<<"sbsbsbsb"<<endl;//无解？？？？？
        }
    }

算法3

(暴力枚举) $O(n^2)$

整体代码：

C++ 代码

#include<bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> ops;

inline int mul(int a,int k) {//慢速幂？？？
    int res=1;
    while(k--) res*=a;
    return res;
}

void cal() {//计算表达式的值 按照后缀表达式的方式
    int num1,num2,num3;
    num1=num.top(); num.pop();
    num2=num.top(); num.pop();
    char op=ops.top(); ops.pop(); 
    if(op=='+') num3=num2+num1;
    else if (op=='-') num3=num2-num1;
    else if (op=='*') num3=num2*num1;
    else if (op=='/') num3=num2/num1;
    else num3=mul(num2,num1);
    num.push(num3);//计算结果压入栈中
}

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,t=0;
            while(str[j]>='0'&&str[j]<='9') {
                t=t*10+str[j]-'0';
                j++;
            }
            num.push(t);//处理多位数字的情况 题目并没有保证是10以内的数字
            i=j-1;
        }
        else {
            char c=str[i];
            if(c=='(') ops.push(c);//左括号 直接入栈 
            else if(c=='+'||c=='-') {
                if(c=='-'&&i&&!(str[i-1]>='0'&&str[i-1]<='9')&&str[i-1]!=')') {//处理负数的情况 将减去一个数 改成+负数 
                    int j=i+1,t=0;
                    while(str[j]>='0'&&str[j]<='9') {
                        t=t*10+str[j]-'0';
                        j++;
                    }
                    num.push(-t);
                    i=j-1;
                }
                else {
                    while(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<<"sbsbsbsb"<<endl;//无解？？？？？
        }
    }
    cout<<num.top()<<endl;
    return 0;
}