题意：

输入一个表达式（用字符串表示），求这个表达式的值。

保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

方法一：

栈

思路：

      利用数字栈、运算符栈和运算符之间的优先级实现。

      实现步骤：

          如果是数字，则入数字栈；

          如果是左括号，则入运算符栈；

          如果是右括号，则匹配相对应的左括号循环运算；

          否则，则根据优先级进行循环计算。（优先级：+、-的优先级小于*、/）.

          注意：添加个优先级为0的等号，以便将运算符栈的运算符遍历完。

#include <bits/stdc++.h>

using namespace std;
map<char,int> m;
string s;
string x="";//数字字符串
stack<int> num;//数字栈
stack<char> op;//运算符栈

int cal(int x,int y,char ch){//四则运算
    switch(ch){
        case '+':
            return x+y;
        case '-':
            return x-y;
        case '*':
            return x*y;
        case '/':
            return x/y;
    }
    return 0;
}
int main(){
    m['+']=m['-']=1;//优先级
    m['*']=m['/']=2;
    m['=']=0;
    cin >> s;
    s+='=';//添加个优先级为0的等号
    int len=s.size();
    for(int i=0;i<len;i++){//遍历
        if(isdigit(s[i])){
            x+=s[i];
        }else{
            if(x.size()){//对数字进行入数字栈
                int sum=0;
                for(int i=0;i<x.size();i++){
                    sum=sum*10+x[i]-'0';
                }
                num.push(sum);
            }
            x="";
            if(s[i]=='('||s[i]=='{'||s[i]=='['){//如果为左括号，入运算符栈
                op.push(s[i]);
            }else if(s[i]==')'){//如果是右括号，则利用匹配左括号循环运算
                while(!op.empty()&&op.top()!='('){
                    int y=num.top();
                    num.pop();
                    int x=num.top();
                    num.pop();
                    char ch=op.top();
                    op.pop();
                    num.push(cal(x,y,ch));
                }
                op.pop();
            }else if(s[i]=='}'){//同理
                while(!op.empty()&&op.top()!='{'){
                    int y=num.top();
                    num.pop();
                    int x=num.top();
                    num.pop();
                    char ch=op.top();
                    op.pop();
                    num.push(cal(x,y,ch));
                }
                op.pop();
            }else if(s[i]==']'){//同理
                while(!op.empty()&&op.top()!='['){
                    int y=num.top();
                    num.pop();
                    int x=num.top();
                    num.pop();
                    char ch=op.top();
                    op.pop();
                    num.push(cal(x,y,ch));
                }
                op.pop();
            }else{
                if(s[i]=='-'&&(s[i-1]=='('||s[i-1]=='['||s[i-1]=='{')){//如果是负数，前面加个0
                    num.push(0);
                }
                while(!op.empty()&&m[s[i]]<=m[op.top()]){//利用优先级进行循环计算
                    int y=num.top();
                    num.pop();
                    int x=num.top();
                    num.pop();
                    char ch=op.top();
                    op.pop();
                    num.push(cal(x,y,ch));
                }
                op.push(s[i]);
            }
        }
    }
    cout << num.top() << endl;//输出数字栈的最后一个数字
    return 0;
}

时间复杂度： $O(n),n是字符串长度，遍历字符串$

空间复杂度： $O(n),n是字符串长度，栈存储运算符和数字$

方法二：

递归

思路：

          递归实现。

          递归的条件是确认区间的左右位置。

          有括号先算括号内的，可知是后序遍历。

          遍历区间内的字符，如果发现有括号，则递归括号内的字符串。

#include <bits/stdc++.h>

using namespace std;
string s;

int f(int l,int r){//递归
    stack<int> num;//数字栈
    int x=0;//存储数字
    char ch='+';//默认
    for(int i=l;i<=r;i++){
        if(s[i]=='('||s[i]=='{'||s[i]=='['){
            int level=1;//层数
            int j=i+1;
            for(;j<=r;j++){
                if(s[j]=='('||s[j]=='{'||s[j]=='[')
                    level++;
                else if(s[j]==')'||s[j]=='}'||s[j]==']')
                    level--;
                if(level==0)//层数等于0，退出
                    break;
            }
            x=f(i+1,j-1);//递归,后序遍历
            i=j+1;
        }else if(isdigit(s[i])){//数字
            x=x*10+s[i]-'0';
        }
        if(!isdigit(s[i])||i>=r){
            int t;
            switch(ch){//包含了运算符优先级的比较
                case '+':
                    num.push(x);
                    break;
                case '-':
                    num.push(-x);
                    break;
                case '*':
                    t=num.top();
                    num.pop();
                    num.push(t*x);
                    break;
                case '/':
                    t=num.top();
                    num.pop();
                    num.push(t/x);
                    break;
            }
            ch=s[i];//上一个运算符
            x=0;
        }
    }
    int sum=0;//累加
    while(!num.empty()){
        sum+=num.top();
        num.pop();
    }
    return sum;
}
int main(){
    cin >> s;
    cout << f(0,s.size()-1) << endl;
    return 0;
}

时间复杂度： $O(n),n是字符串长度，遍历字符串$

空间复杂度： $O(n),n是字符串长度，递归栈的最大深度。$

题解 | #四则运算#

全站热榜

创作者周榜