201903-2 二十四点

输入输出样例

样例1

输入

10
9+3+4x3
5+4x5x5
7-9-9+8
5x6/5x4
3+5+7+9
1x1+9-9
1x9-5/9
8/5+6x9
6x7-3x6
6x4+4/5

输出

Yes
No
No
Yes
Yes
No
No
No
Yes
Yes

题解一

参见中缀表达式求值。100分。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        for (int i = 0; i < n; ++i) {
            int ans = cal(reader.readLine().trim());
            if (ans == 24) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
    private static int cal(String s) {
        return calculate(infixToPostfix(infixToList(s)));
    }
    private static List<String> infixToList(String expression) {
        List<String> ans = new LinkedList<String>();
        char[] chars = expression.toCharArray();
        for (int begin = 0, i = 0; i < chars.length;) {
            // 符号
            if ((chars[i] < '0') || (chars[i] > '9')) {
                ans.add(chars[i] + "");
                ++i;
                begin = i;
            } else { // 整字
                while ((i < chars.length) && (chars[i] >= '0') && (chars[i] <= '9')) {
                    ++i;
                }
                ans.add(expression.substring(begin, i));
                begin = i;
            }
        }
        return ans;
    }
    private static List<String> infixToPostfix(List<String> infixList) {
        List<String> ans = new ArrayList<>(infixList.size());
        // 符号栈
        Deque<String> stack = new LinkedList<>();
        for (String e : infixList) {
            if (e.equals("(")) { // 左括号直接入栈
                stack.push(e);
            } else if (e.equals(")")) { // 右括号入栈时, 一直出栈直到遇到将知道一个左括号
                while (!stack.peek().equals("(")) {
                    // 栈顶元素出栈入队
                    ans.add(stack.pop());
                }
                // 左括号直接出栈
                stack.pop();
            } else if (isOperator(e)) { // 遇到操作符
                // 栈为空或者栈顶元素优先级低则入栈
                if (stack.isEmpty() || (getPriority(stack.peek()) < getPriority(e))) {
                    stack.push(e);
                } else {
                    // 栈不为空且栈顶元素不为左括号且栈顶元素优先级大于党员元素, 则持续出栈入队
                    while ((!stack.isEmpty()) && (!stack.peek().equals("("))
                            && (getPriority(stack.peek()) >= getPriority(e))) {
                        ans.add(stack.pop());
                    }
                    stack.push(e);
                }
            } else { // 遇到数字, 直接入队
                ans.add(e);
            }
        }
        while (!stack.isEmpty()) {
            ans.add(stack.pop());
        }
        return ans;
    }
    private static boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("x") || s.equals("/");
    }
    private static int getPriority(String s) {
        switch (s) {
        case "+":
        case "-":
            return 1;
        case "x":
        case "/":
            return 2;
        }
        // 左括号优先级最低
        return -1;
    }
    private static int calculate(List<String> list) {
        // 结果栈
        Deque<Integer> stack = new LinkedList<>();
        int num1, num2;
        for (String e : list) {
            if (isOperator(e)) {
                num2 = stack.pop();
                num1 = stack.pop();
                switch (e) {
                case "+":
                    stack.push(num1 + num2);
                    break;
                case "-":
                    stack.push(num1 - num2);
                    break;
                case "x":
                    stack.push(num1 * num2);
                    break;
                case "/":
                    stack.push(num1 / num2);
                    break;
                }
            } else {
                stack.push(Integer.parseInt(e));
            }
        }
        return stack.pop();
    }
}