AcWing 454. 表达式求值
宋标 Lv5
  2022-08-18 02:31:21 2022-08-18 02:31    

题目

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入格式

输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 + 和乘法运算符 *，且没有括号，所有参与运算的数字均为 到 之间的整数。

输入数据保证这一行只有 、、 这 种字符。

输出格式

输出只有一行，包含一个整数，表示这个表达式的值。

注意：当答案长度多于 位时，请只输出最后 位，前导 不输出。

数据范围

表达式中加法运算符和乘法运算符的总数

输入样例：

1+1000003*1

输出样例：

4

题解

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 100010, M = 10000;

int num_s[N], op_s[N];
int ntt = 0, ott = 0;

void op()
{
    int res = 0;
    int t1 = num_s[ntt --], t2 = num_s[ntt --];

    if (op_s[ott] == '+') res = (t1 % M + t2 % M) % M;
    else res = (t1 % M) * (t2 % M) % M;

    num_s[++ ntt] = res ;
    -- ott;
}

int main()
{
    string s; cin >> s;
    unordered_map<char, int> order = {{'*', 1}, {'+', 0}};

    for (int i = 0; i < s.size(); ++ i)
    {
        if (isdigit(s[i]))
        {
            int t = s[i] - '0';
            while (i + 1 < s.size() && isdigit(s[i + 1]))
                t *= 10, t += s[i + 1] - '0', ++ i;
            num_s[++ ntt] = t;
        }
        else 
        {
            // 如果运算符栈顶优先级大于等于当前运算符需运算
            if (ott && order[op_s[ott]] >= order[s[i]]) op();
            op_s[++ ott] = s[i];
        }
    }
    // 操作剩余的运算符
    while (ott) op();

    cout << num_s[ntt] % M << endl;

    return 0;
}
 评论