原题
二十四点是一款著名的纸牌游戏,其游戏的目标是使用 3 个加减乘除运算使得 4张纸牌上数字的运算结果为 24。
题目
定义每一个游戏由 4 个从 1-9 的数字和 3 个四则运算符组成,保证四则运算符将数字两两隔开,不存在括号和其他字符,运算顺序按照四则运算顺序进行。其中加法用符号 + 表示,减法用符号 - 表示,乘法用小写字母 x 表示,除法用符号 / 表示。在游戏里除法为整除,例如 2 / 3 = 0,3 / 2 = 1, 4 / 2 = 2。
老师给了你 n 个游戏的解,请你编写程序验证每个游戏的结果是否为 24 。
输入
从标准输入读入数据。第一行输入一个整数 n,从第 2 行开始到第 n + 1 行中,每一行包含一个长度为 7的字符串,为上述的 24 点游戏,保证数据格式合法。
输出
输出到标准输出。
包含 n 行,对于每一个游戏,如果其结果为 24 则输出字符串 Yes,否则输出字符串 No。
输入样例
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
样例解释
9+3+4 × 3 = 24
5+4 × 5 × 5 = 105
7 − 9 − 9+8= −3
5 × 6/5 × 4 = 24
3 + 5 + 7 + 9 = 24
1 × 1+9 − 9=1
1 × 9 − 5/9 = 9
8/5 + 6 × 9 = 55
6 × 7 − 3 × 6 = 24
6 × 4 + 4/5 = 24
解析:
看到这个题目的第一眼,马上就联想到了这个学期学习编译原理中的词法分析,关键在于这个算法是先乘除后加减,所以一般考虑用栈来解决
两次循环,第一次将所有字符入栈,并且将乘除法算完
第二次再算完加减法,栈中只剩最后一个字符时
判定是否是24即可
以下是10分答案(我也很无奈,我觉得没问题)
import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++) {
String s = sc.next();
char[] ch = s.toCharArray();
Stack<Character> stack = new Stack<>();
for (int j = 0; j < ch.length; j++) {
stack.push(ch[j]);
//由于没有括号,遇到乘除先算乘除
if (stack.peek() == 'x' || stack.peek() == '/') {
//还需再添加一个乘数或者除数
stack.push(ch[++j]);
//避免异常,加判定
if (stack.size() >= 3)
caculate(stack);
}
}
//乘除已经算完了,现在栈中只需要执行加减运算,当栈中只有一个数时,那就是答案
while (stack.size() != 1) {
caculate(stack);
}
//由于栈中是字符,转化为数字时要减去48
if (stack.pop()-48 == 24) {
System.out.println("YES");
} else System.out.println("No");
}
}
//这个方法封装对栈中后三个字符执行一次运算,再把运算结果加入栈中
public static void caculate(Stack<Character>stack){
//从栈顶取出要运算的三个字符
int second=stack.pop()-48;
char sign=stack.pop();
int first=stack.pop()-48;
int res=0;
switch (sign){
case '+':
res=first+second;
break;
case '-':
res=first-second;
break;
case 'x':
res=first*second;
break;
case '/':
res=first/second;
break;
}
//整型转化为字符也要加上48,不加语法上不会错,但是会和上面的不匹配,会算出其他意想不到的值
stack.push((char)(res+48));
}
}
输出结果
事实上,编译器检查右括号是否漏写时,左右括号是否匹配时也是用栈,比如先把左小括号入栈,然后如果最后对应的右括号没有入栈,那么就报错,如果入的是右中括号,也报错
如果入的是右小括号,那么两个一起出栈
这种类似的线性匹配问题,往往用栈来解决
以下是100分答案
还是python好
n=int(input())
for j in range(n):
alg=input()
res=[alg[0]]
i=1
#这里不能用for i in range(1,len(alg)),否则i将会按1,2,3……一直到末尾,我们在下面对i的修改将失效,也不能直接在alg上修改,因为要考虑先乘除后加减,必然要多次遍历
while i < len(alg):
if alg[i]=='x':
res.append(int(res.pop(-1))*int(alg[i+1]))
i+=2
elif alg[i]=='/':
res.append(int(res.pop(-1))//int(alg[i+1]))
i+=2
else:
res.append(alg[i])
i+=1
alg=res
res=[alg[0]]
i=1
while i < len(alg):
if alg[i]=='+':
res.append(int(res.pop(-1))+int(alg[i+1]))
i+=2
elif alg[i]=='-':
res.append(int(res.pop(-1))-int(alg[i+1]))
i+=2
else:
res.append(alg[i])
i+=1
if int(res[0])==24:
print("Yes")
else :
print("No")