后缀表达式简易计算器

Quartz_Blocks · 2024-04-21 11:31:34 · 算法·理论

简易后缀表达式计算器

后缀表达式不懂的可以上网看（提供一个链接↓）。

后缀表达式教程1

原理：将一个中缀表达式（我们平常的 1+1 就是中缀表达式，符号在中间）转换为后缀表达式，再计算出后缀表达式的值。

因为代码长，不要放在洛谷在线IDE里面跑（卡评测机），编译大约需要 10 秒左右（悲

#include<bits/stdc++.h>
using namespace std;
map<char, int> mp;//优先级map声明

int res(string s){//将之前做好的后缀表达式计算结果
    stack <int> a;//数字stack
    int len = s.length();

    cout << "开始计算后缀表达式" << endl;
    for(int i = 0;i < len;i++){
        if(s[i] == '.'){//由于我使用.作为分解，这里需要处理
            continue;
        }else if(s[i] == '+'){
            int y = a.top();
            a.pop();
            int x = a.top();
            a.pop();
            a.push(x+y);
        }else if(s[i] == '-'){
            int y = a.top();
            a.pop();
            int x = a.top();
            a.pop();
            a.push(x-y);
        }else if(s[i] == '*'){
            int y = a.top();
            a.pop();
            int x = a.top();
            a.pop();
            a.push(x*y);
        }else if(s[i] == '/'){
            int y = a.top();
            a.pop();
            int x = a.top();
            a.pop();
            a.push(x/y);
        }else{
            string num = "";//用string临时存储
            while(s[i] != '.'){//读入多位数（小于2^31-1）
                num += s[i];
                i++;
            }
            cout << "数字处理 字符型数字：" <<num << "，数字型数字：" ;
            int numlen = num.length();
            int j = numlen-1;
            int sum = 0;//求出数字的int形式
            for(int i = 0;i < numlen;i++,j--){
                sum += (num[i]-'0')*pow(10,j);
            }
            cout << sum  << "。\n";
            a.push(sum);
        }
    }
    return a.top();
} 
string make(string s){//s 当前的中缀表达式
    string res = "",x = "";//res 最终输出后缀表达式 x 临时存储的数字
    stack <char> a;
    int len = s.length();
    cout << "开始制作表达式" << endl;
    for(int i = 0;i < len;i++){
        cout << s[i] << endl;
        if(s[i] <= '9' && s[i] >= '0'){
            x += s[i];
        }else{
            res += '.'+x + '.';
            x = "";
            if(s[i] == '+' || s[i] == '-'){
                if(s[i] == '+'){
                    if(a.empty()){
                        a.push(s[i]);
                    }else if(a.top() == '('){
                        a.push(s[i]);
                    }else{
                        while(1){//为了防止爆栈，我使用了带break的死循环
                            if(a.empty()){
                                break;
                            }else if(mp[a.top()] > 1){//优先级更高
                                res += a.top();
                                a.pop();
                            }else{
                                break;
                            }
                        }
                    }
                }
                if(s[i] == '-'){
                    if(a.empty()){
                        a.push(s[i]);
                    }else if(a.top() == '('){
                        a.push(s[i]);
                    }else{
                        while(1){
                            if(a.empty()){
                                break;
                            }else if(mp[a.top()] > 1){
                                res += a.top();
                                a.pop();
                            }else{
                                break;
                            }
                        }
                    }
                }
            }else if(s[i] == '*' || s[i] == '/'){
                if(s[i] == '*'){
                    if(a.empty()){
                        a.push(s[i]);
                    }else if(a.top() == '(' || a.top() == '+' || a.top() == '-'){
                        a.push(s[i]);
                    }else{
                        res += s[i];
                    }
                }
                if(s[i] == '/'){
                    if(a.empty()){
                        a.push(s[i]);
                    }else if(a.top() == '(' || a.top() == '+' || a.top() == '-'){
                        a.push(s[i]);
                    }else{
                        res += s[i];
                    }
                }
            }else if(s[i] == '('){//括号优先级可以设为最低，这样就保证了括号不会被踢
                a.push(s[i]);           
            }else{
                while(a.top() != '('){
                    res += a.top();
                    a.pop();
                }
                a.pop();
            }
        }

    }
    res += '.'+x+'.';
    while(!a.empty()){
        res += a.top();
        a.pop();
    }
    return res;
}
int main(){
    cout << "开始" << endl;
    mp['+'] = 1;//设置优先级
    mp['-'] = 1;
    mp['*'] = 2;
    mp['/'] = 2;
    mp['('] = 0;    
    string a,b;
    cout << "赋值完成" << endl;
    cin >> a;
    b = make(a);
    cout << "后缀表达式制作完成，表达式为" << b << endl;
    cout << res(b) << endl;
    cout << "程序结束" << endl;
    return 0;
}