逆波兰表达式

· · 个人记录

只是给自己用

逆波兰表达式，又叫后缀表达式

测试数据

1、输入82 3 20 8-*2/+

输出100

2、输入15 2 3 *+189+

输出210

正常的中缀表达组转逆波兰表达式

例：1)82+3*(20-8)/2

2)1+2-3*4/5

（1） 根据运算符的优先级对中缀表达式加括号

对例子进行操作之后变成这个表达式：1)(82+((3*(20-8))/2))

2)((1+2)-((3*4)/5))

（2）运算符移到对应括号的后面

操作后变成这个表达式：1)(无括号)82 3 20 8-*2/+

2）((1 2+)((3 4*)5/)-)

（3）（可以省略）去括号

例1)略

2)1 2+3 4*5/-

正常的中缀表达组转波兰表达式

和逆波兰表达式的转换相反

（1） 先加括号

对例子进行操作之后变成这个表达式：1)(82+((3*(20-8))/2))

2)((1+2)-((3*4)/5))

（2）运算符移到对应括号的前面

操作后变成这个表达式：1)(无括号)+82 /*3- 20 8 2

2）(-(+1 2)(/(*3 4)5)

（3）（可以省略）去括号

例1)略

2)- +1 2/*3 4 5

计算规则

逆波兰表达式↓

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> stk;
    string s;
    getline(cin,s);
    int len = s.size();
    //从左到右遍历表达式
    for (int i=0; i<len; i++) {

        //如果碰到数字则入栈
        int sum=0;  //组合操作数
        while ('0'<=s[i] && s[i]<='9') {
            sum=sum*10+s[i]-48;
            i++;
        }
        if (sum) stk.push(sum);
        //遇到符号，首先弹出第二操作数，再次弹出第一操作数，再把答案push回去
        if (s[i]=='+' || s[i]=='*' || s[i]=='/' || s[i]=='-') {
            int num2=stk.top();
            stk.pop();
            int num1=stk.top();
            stk.pop();
            switch (s[i]) {
                case '+':
                    stk.push(num1+num2);
                    break;
                case '-':
                    stk.push(num1-num2);
                    break;
                case '*':
                    stk.push(num1*num2);
                    break;
                case '/':
                    stk.push(num1/num2);
                    break;
            }
        }
    }
    cout<<stk.top();
    return 0;
}

大根堆优先队列（默认）↓

#include <bits/stdc++.h>
using namespace std;
priority_queue <int> q;
int main(){
    srand(time(0));
    int n=10;
    for (int i=1;i<=10;i++){
        int t=rand()%50000;
        cout<<t<<' ';
        q.push(t);
    }
    cout<<endl;
    while (q.size()){
        cout<<q.top()<<' ';
        q.pop();
    }
    return 0;
}

小根堆优先队列↓

#include <bits/stdc++.h>
using namespace std;
priority_queue <int,vector<int>,greater<int> > q;
int main(){
    srand(time(0));
    int n=10;
    for (int i=1;i<=10;i++){
        int t=rand()%50000;
        cout<<t<<' ';
        q.push(t);
    }
    cout<<endl;
    while (q.size()){
        cout<<q.top()<<' ';
        q.pop();
    }
    return 0;
}