【每日一题 春季3】3302. 表达式求值 & 150. 逆波兰表达式求值

发表于 分类于 Valine：
本文字数： 71 阅读时长 ≈ 1 分钟

Day3 AcWing 3302. 表达式求值
Day3 LeetCode 150. 逆波兰表达式求值

思路

  1. 栈

代码

3302. 表达式求值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}
150. 逆波兰表达式求值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> st;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int num1 = st.back();
                st.pop_back();
                int num2 = st.back();
                st.pop_back();
                if (tokens[i] == "+") st.push_back(num2 + num1);
                if (tokens[i] == "-") st.push_back(num2 - num1);
                if (tokens[i] == "*") st.push_back(num2 * num1);
                if (tokens[i] == "/") st.push_back(num2 / num1);
            } else {
                st.push_back(stoi(tokens[i]));
            }
        }
        int result = st.back();
        st.pop_back(); // optional
        return result;
    }
};