二十四点

题目描述

给定一个只包含数字1-9、加减乘除运算符和等号的表达式，验证结果是否等于24。

运算符优先级：乘除高于加减，同优先级从左到右计算，等号表示表达式结束。

算法思路

使用栈进行表达式求值：

1. 读取数字和运算符，数字直接入栈
2. 遇到运算符时，如果栈顶有运算符且优先级不高于当前运算符，则先计算栈顶的运算
3. 否则将当前运算符入栈
4. 表达式结束时，清空栈中剩余运算

对于二十四点问题，运算符只有加减乘除，无括号，按从左到右计算即可。

代码实现

#include <bits/stdc++.h>
using namespace std;
 
int calc(int a, int b, char op){
    if(op == '+') return a + b;
    if(op == '-') return a - b;
    if(op == '*') return a * b;
    if(op == '/') return a / b;
    return 0;
}
 
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    string s;
    cin >> s;
    
    stack<int> nums;
    stack<char> ops;
    
    int i = 0;
    while(i < s.size()){
        if(isdigit(s[i])){
            nums.push(s[i] - '0');
        }else if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/'){
            // 二十四点：乘除优先级高于加减，同级从左到右
            while(!ops.empty() && (ops.top() == '*' || ops.top() == '/') && 
                  (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')){
                // 先计算栈中的乘除
                char op = ops.top(); ops.pop();
                int b = nums.top(); nums.pop();
                int a = nums.top(); nums.pop();
                nums.push(calc(a, b, op));
            }
            ops.push(s[i]);
        }
        i++;
    }
    
    // 计算剩余运算
    while(!ops.empty()){
        char op = ops.top(); ops.pop();
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        nums.push(calc(a, b, op));
    }
    
    cout << (nums.top() == 24 ? "true" : "false") << endl;
    return 0;
}

关键点

• 使用两个栈：操作数栈和运算符栈
• 乘除优先级高于加减
• 同优先级从左到右计算
• 注意除法为整数除法

参考

• CCF-CSP认证