xiaomi

个人博客

小米的个人博客,欢迎交流


CCF满分代码-[用栈实现]24点[201903-2题]


题目描述

1903_2

思路

按照我们超强人脑一眼就可以看出公式的运算顺序,但是如何才能让代码也如此 “智能” ?

对给出的样例演算几遍可以发现 ,无论乘除号位于何处,我们总是最先把他们找出来计算就好,我们可以根据 数据结构来完成这一操作。

遍历公式字符串,每一个数字无论后面的运算符是什么都先 push操作,然后再来判断符号来决定下一步

  • 如果是 加号,我们直接把后面的数字 压栈
  • 如果是 减号,先把数字 取反再压栈
  • 如果是 乘号或除号,把 栈顶取出与后面的数字做乘法/除法

接下来再处理加号与减号,实际上只有加法运算了,因为减数已经经过处理变成了相反数

  • 将栈内元素累加
  • 最后判断结果是否是24

图解

1903_2图解

代码

import java.util.Scanner;
import java.util.Stack;

public class CCF201903_2 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        while (n-- > 0) {
            Stack stack = new Stack();
            String ask = in.next();
            
            stack.push(ask.charAt(0) - '0');
            for (int i = 2; i < ask.length(); i += 2) {
                if (ask.charAt(i - 1) == '+') {
                    stack.push(ask.charAt(i) - '0');
                } else if (ask.charAt(i - 1) == '-') {
                    stack.push(-(ask.charAt(i) - '0'));
                } else if (ask.charAt(i - 1) == 'x') {
                    int num = ask.charAt(i) - '0';
                    int top = (int) stack.pop();
                    top *= num;
                    stack.push(top);
                } else if (ask.charAt(i - 1) == '/') {
                    int num = ask.charAt(i) - '0';
                    int top = (int) stack.pop();
                    top /= num;
                    stack.push(top);
                }
            }
            
            int res = (int) stack.pop();
            while (!stack.isEmpty()) {
                res += (int) stack.pop();
            }

            if (res == 24) {
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }
}

/*
-------input
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
-------output
Yes
No
No
Yes
Yes
No
No
No
Yes
Yes
 */