盛日辉的博客
0%

EOJ 1836. 表达式

发表于 分类于

一道用 Python 一下子就一行带走的题，但竟然还有高级做法……

题目

题目链接

Python 一行流

1
print(eval(input().replace("/", "//")))

也有写成 print(int(eval(input()))) 这样的。但我觉得题目里的 / 应当是 整除 ，最好换成 Python 的 // 更好一些。

双栈模拟

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
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

int main() {
    const unordered_map<char, int>
        op_priority = {
            {'+', 0},
            {'-', 0},
            {'*', 1},
            {'/', 1},
            {'(', -1}};
    string s;
    cin >> s;
    vector<char> op;
    vector<int> num;
    auto func = [&]() {
        int y = num.back();
        num.pop_back();
        int x = num.back();
        num.pop_back();
        char o = op.back();
        op.pop_back();
        int res = 0;
        if (o == '+') res = x + y;
        else if (o == '-') res = x - y;
        else if (o == '*') res = x * y;
        else res = x / y;
        num.push_back(res);
    };

    num.push_back(0);
    for (int idx = 0; idx < s.size(); idx++) {
        char c = s[idx];
        if (isdigit(c)) {
            int x = num.back() * 10 + c - '0';
            num[num.size() - 1] = x;
        } else if (c == '(') {
            op.push_back(c);
        } else if (c == ')') {
            while (op.back() != '(') {
                func();
            }
            op.pop_back();
        } else if (c == '-' && (op.empty() || s[idx - 1] == '(')) {
            // 负数
            num.push_back(0);
            op.push_back('-');
        } else if (!op.empty() && op_priority.at(c) <= op_priority.at(op.back())) {
            while (!op.empty() && op_priority.at(c) <= op_priority.at(op.back()))
                func();
            op.push_back(c);
            num.push_back(0);
        } else {
            // 其他运算符
            op.push_back(c);
            num.push_back(0);
        }
    }
    // 收尾
    while (!op.empty()) func();
    cout << num[0];
    return 0;
}
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
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
int main() {
    const unordered_map<char, int>
        op_priority = {
            {'+', 0}, {'-', 0}, {'*', 1}, {'/', 1}, {'(', -1}};
    string s;
    cin >> s;
    vector<char> op;
    vector<int> num;
    auto func = [&]() {
        int y = num.back();
        num.pop_back();
        int x = num.back();
        num.pop_back();
        char o = op.back();
        op.pop_back();
        int res = 0;
        if (o == '+') res = x + y;
        else if (o == '-') res = x - y;
        else if (o == '*') res = x * y;
        else res = x / y;
        num.push_back(res);
    };
    int n = s.size();
    for (int idx = 0; idx < n; idx++) {
        char c = s[idx];
        if (isdigit(c)) {
            int x = 0;
            while (idx < n && isdigit(s[idx]))
                x = x * 10 + s[idx++] - '0';
            idx--;  // 等会在 for 那里还要 ++
            num.push_back(x);
        } else if (c == '(') {
            op.push_back(c);
        } else if (c == ')') {
            while (op.back() != '(') {
                func();
            }
            op.pop_back();
        } else {
            // 负数，开头和 (- 的情况
            if (c == '-' && (idx == 0 || s[idx - 1] == '(')) {
                num.push_back(0);
            }
            // 只要栈顶优先级 >= 当前，就一直算
            while (!op.empty() && op_priority.at(c) <= op_priority.at(op.back()))
                func();
            op.push_back(c);
        }
        cout << s << "\n";
        cout << s[idx]<< "\n";
        cout << "op:  ";
        for(char o: op) cout << o << " ";
        cout << "\nnum: ";
        for(int x: num) cout << x << " ";
        cout << "\n\n";
    }
    while (!op.empty()) func();
    cout << num[0];
    return 0;
}

终极递归

这个方法感觉听精妙的。用三个函数分别处理不同优先级的计算，

  • exp() ：表达式级别和加减法；
  • term() ：乘除法；
  • factor() ：一个数，包括一个括号的结果；

exp() 调用 term() ，term() 调用 factor() ，若 factor() 里又遇到括号，就又重新调用 exp() 。

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
#include <bits/stdc++.h>
using namespace std;
int p; // 全局变量，在表达式里的下标
string s;
int term();
int exp();

// 处理一个数（包括一个括号的结果）
int factor(){
    int val = 0;
    if(s[p] == '('){
        p++;
        val = exp(); // 算括号的值
        p++; // 跳过右括号
        // 上面三行可以写成 p++, val = exp(), p++;
    }else{
        while(p < s.size() && isdigit(s[p]))
            val = val * 10 + s[p++] - '0';
    }
    return val;
}

// 计算乘除（最高优先级）
int term(){
    int val = factor(); // 先拿到一个数
    while(s[p] == '*' || s[p] == '/'){
        if(s[p] == '*')
            p++, val *= factor();
        else
            p++, val /= factor();
    }
    return val;
}

// 计算整个表达式和处理加减（低优先级）
int exp(){
    int val = term();
    while(s[p] == '+' || s[p] == '-')
        if(s[p] == '+')
            p++, val += term();
        else
            p++, val -= term();
    return val;
}

int main(){
    cin >> s;
    p = 0;
    cout << exp();
    return 0;
}

奇技淫巧

调用命令行~

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
#include <iostream>
#include <string>
#include <cstdlib>   // 包含 system() 函数
#include <cstdio>    // 包含 popen/pclose（可选，更优雅的结果获取方式）

int main() {
    // 1. 接收用户输入的表达式字符串
    std::string expr;
    std::getline(std::cin, expr);  // 读取带空格的完整表达式

    // 2. 拼接 Shell/CMD 命令（调用 eval 计算）
    std::string cmd;
    {
        // Linux/Mac bash 语法：用 eval 执行 $(( )) 计算
        cmd = "eval \"result=$(( " + expr + " ))\" && echo \"$result\"";
    }

    // 3. 执行命令并输出结果
    int ret = system(cmd.c_str());  // 执行拼接后的命令

    // 4. 错误处理
    if (ret != 0) {
        std::cerr << "\n错误：表达式格式无效或计算失败！" << std::endl;
        return 1;
    }

    return 0;
}