讨论/算法和数据结构/CCF 二十四点问题求解/
CCF 二十四点问题求解

题目如下:
1567587195_312436.png

我的代码如下:

import java.util.Scanner;

public class 二十四点 {
    public static void main(String[] args) {

        Scanner s =  new Scanner(System.in);
        int n = s.nextInt();
        String strs[] = new String[n];
        for(int i = 0;i < n;i++) {
            strs[i] = s.next();
        }
        for (int j = 0; j < n;j++){
            if(calc(strs[j]) == 24){
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }
        public static  int calc(String str){
            int res = 0;
            char chars[] = str.toCharArray();
            //中缀表达式转后缀表达式
            Stack stack = new Stack(10);
            String postfix = "";
            for (int i=0;i<chars.length;i++){
                if (chars[i] > '9' || chars[i] < '0'){   //只要不是数字必定是操作符  操作符要出栈到“小于”当前操作符优先级
                    while (stack.peek()=='x' || stack.peek()=='/' ||stack.peek() == 'X'){
                        postfix +=stack.pop();
                    }
                    stack.push(chars[i]);
                }
                else{
                    postfix += chars[i];
                }
            }
            while (!stack.isEmpty()){
                    postfix += stack.pop();
                }
            //计算后缀表达式
            Stack calcStack = new Stack(10);
            char postfixs[] = postfix.toCharArray();    
            for (int i = 0; i < postfixs.length ; i++){
                if (postfixs[i] >= '0' && postfixs[i] <= '9'){
                    calcStack.push(postfixs[i]);
                }else{
                    int right = 0;
                    switch (postfixs[i]){
                        case 'x':
                        case 'X':
                            res =(calcStack.pop()-'0') * (calcStack.pop()-'0');
                            calcStack.push((char)((int)'0'+res));
                            break;
                        case '/':
                            right = calcStack.pop()-'0';
                            res =((calcStack.pop()-'0') / right);
                            calcStack.push((char)((int)'0'+res));
                            break;
                        case '+':
                            res =(calcStack.pop()-'0' )+ (calcStack.pop()-'0');
                            calcStack.push((char)((int)'0'+res));
                            break;
                        case '-':
                            right = calcStack.pop()-'0';
                            res = (calcStack.pop()-'0') - right;
                            calcStack.push((char)((int)'0'+res));
                            break;
                    }
                }
            }
            res = calcStack.pop() - '0';
            return res;
        }
    }
class Stack{
    private int maxSize;
    private char stackArray[];
    private int top;
    public Stack(int max){
        maxSize = max;
        stackArray = new char[max];
        top = -1;
    }
    public char pop() {
        return stackArray[top--];
    }
    public void push(char x){
        stackArray[++top] = x;
    }
    public char peek(){
        if (top != -1)
            return stackArray[top];
        else
            return  ' ';
    }
    public boolean isEmpty(){
        return top==-1;
    }
}


虽然通过了题目带的十个用例,但是提交后的成绩只有30分,求大神解答!

展开讨论
DeH40发起于 2019-09-05
最近编辑于 2019-09-07

总共就只有3个符号,四个数字,因此先转后缀在求值太没必要了。可以发现当前符号只与与他相邻的符号有关因此一次只需判断相邻两个
符号的优先级直接计算就好了。
比如8 / 5 + 6 * 9
/ > + 故先计算 8/5 变为 1 + 6 * 9 而 * > + 故先计算 6 * 9 变为 1 + 54 = 55
线性时间复杂度,这是我的一点看法

展开全部 2 讨论