后缀表达式的值

胡兜兜玩算法 / 2023-08-30 / 原文

问题提出

从键盘读入一个后缀表达式（字符串），只含有0-9 组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。

提示：输入字符串长度小于250，参与运算的整数及结果之绝对值均在2^64
范围内，如有除法保证能整除。

解题思路

我们先准备一个栈 s_num 和一个队列 s_op ，分别用来存数字和符号

如果下一个输入的不是‘@’，就继续执行

如果下一个输入的是‘+’、‘-’、‘*’、‘/’

	getchar
	s_op.push ch
	
如果下一个是‘ ’

	getchar
	
如果都不是

	cin num
	s_num.push num

calc
没什么好说的，每次获得栈的头和第二个元素，再获得队列的头，作为num1,num2,op计算。
if...

else if...

else···

就行了

AC代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    stack<long> s_num;
    queue<char> s_op;//数组也行，但是他没有push/pop操作
    char op;
    long n1, n2;
    //input and push
    char c;
    while((c = cin.peek()) != '@') {
        if(c == '+' || c == '-' || c == '*' || c == '/') {
            getchar();
            s_op.push(c);
        } else if(c == ' ') {
            getchar();
        } else {
            cin >> n1;
            s_num.push(n1);
        }
    }
    //calc
    while(!s_op.empty()) {
        op = s_op.front();
        s_op.pop();
        n1 = s_num.top();
        s_num.pop();
        n2 = s_num.top();
        s_num.pop();
        if(op == '+')//不太喜欢用switch,每次都要用break
            s_num.push(n1 + n2);
        else if(op == '-')
            s_num.push(n2 - n1);
        else if(op == '*')
            s_num.push(n1 * n2);
        else
            s_num.push(n2 / n1);
    }
    cout << s_num.top();
    return 0;
}