洛谷P1449 后缀表达式题解栈

题目链接：https://www.luogu.org/problem/P1449

这道题目我们只需要开一个栈，每次读取到一个数的话就将这个数 push 进栈。

因为提供给我们的时候已经是一个后续序列了，所以能保证每次遇到一个符号的时候栈中至少有2个元素。

我们先从栈中取出一个元素，设为 \(a\) ；再从栈中取出一个元素，设为 \(b\) 。那么，对于符号来说：

如果它是 + ，那么将 \(b+a\) 的结果 push 进栈；
如果它是 - ，那么将 \(b-a\) 的结果 push 进栈；
如果它是 * ，那么将 \(b*a\) 的结果 push 进栈；
如果它是 / ，那么将 \(b/a\) 的结果 push 进栈。

最终能保证栈中只有一个元素，即栈顶元素，它就是我们后缀表达式的结果。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010;

int n, c;

char s[maxn];

stack<int> stk;

int main() {

    cin >> s;

    n = strlen(s);

    n --;   // 因为最后一个是 '@'

    int i = 0;

    while (i < n) {

        if (isdigit(s[i])) {

            c = 0;

            while (i < n && isdigit(s[i])) {

                c = c * 10 + s[i] - '0';

                i ++;

            }

            stk.push(c);

            i ++;

        }

        else {

            int a = stk.top(); stk.pop();

            int b = stk.top(); stk.pop();

            if (s[i] == '+') stk.push(b + a);

            else if (s[i] == '-') stk.push(b - a);

            else if (s[i] == '*') stk.push(b * a);

            else stk.push(b / a);

            i ++;

        }

    }

    cout << stk.top() << endl;

    return 0;

}

巴特西

洛谷P1449 后缀表达式题解栈

最新文章

热门文章

巴特西

洛谷P1449 后缀表达式 题解 栈

最新文章

热门文章

洛谷P1449 后缀表达式题解栈