【问题描述】
明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解决这个问题。假设你是明明,能完成这个任务吗?
这个选择题中的每个表达式都满足下面的性质:
1. 表达式只可能包含一个变量‘a’。
2. 表达式中出现的数都是正整数,而且都小于10000。
3. 表达式中可以包括四种运算‘+’(加),‘-’(减),‘*’(乘),‘^’(乘幂),以及小括号‘(’,‘)’。小括号的优先级最高,其次是‘^’,然后是‘*’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。(注意:运算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’,‘)’都是英文字符)
4. 幂指数只可能是1到10之间的正整数(包括1和10)。
5. 表达式内部,头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子:
((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1 + (a -1)^3,1^10^9……
【输入文件】
输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n(2 <= n <= 26),表示选项的个数。后面n行,每行包括一个选项中的表达式。这n个选项的标号分别是A,B,C,D……
输入中的表达式的长度都不超过50个字符,而且保证选项中总有表达式和题干中的表达式是等价的。
【输出文件】
输出文件equal.out包括一行,这一行包括一系列选项的标号,表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列,而且之间没有空格。
【样例输入】
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a –a
【样例输出】
AC
【数据规模】
对于30%的数据,表达式中只可能出现两种运算符‘+’和‘-’;
对于其它的数据,四种运算符‘+’,‘-’,‘*’,‘^’在表达式中都可能出现。
对于全部的数据,表达式中都可能出现小括号‘(’和‘)’。
【 问题解答】
在做这个题的时候参考了网友的思路。
package com.danan;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.Scanner;
import java.util.Stack;
import java.util.logging.Logger;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Noi05 {
public static final String IN_PATH = "equal.txt";
public static final String OU_PATH = "D:/rs.txt";
private static Logger log = Logger.getLogger("com.danan.Noi05");
private String express = null;
private Integer a = null;
private String exps[] = null;
/**
* @param args
*/
public static void main(String[] args) {
Noi05 noi05 = new Noi05();
noi05.wirteAnswer();
}
public Noi05() {
super();
init();
}
private void init() {
Scanner scanner = new Scanner(
ClassLoader.getSystemResourceAsStream(IN_PATH));
express = scanner.nextLine();
a = Integer.parseInt(scanner.nextLine());
exps = new String[a];
for (int i = 0; i < a; i++) {
exps[i] = scanner.nextLine();
}
scanner.close();
}
public void wirteAnswer() {
Long result = process(express);
log.info("result:" + result);
Long tempRs = null;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < exps.length; i++) {
tempRs = process(exps[i]);
log.info("exps[" + i + "]:" + tempRs);
if (result.equals(tempRs)) {
sb.append((char) (i + 65));
}
}
// write result to file
OutputStream os = null;
try {
os = new FileOutputStream(OU_PATH);
os.write(sb.toString().getBytes());
log.info("write '" + sb.toString() + "' to File" + OU_PATH);
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
os.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
private Long process(String exp) {
Stack<String> maskSK = new Stack<String>();
Stack<Long> numSK = new Stack<Long>();
Pattern pattern = Pattern.compile("\\D|\\d+");
Matcher matcher = pattern.matcher(exp);
String mask = null;
while (matcher.find()) {
mask = matcher.group();
if (isMask(mask)) {
maskSKProcess(maskSK, numSK, mask);
} else {
numSK.push("a".equals(mask) ? a : Long.parseLong(mask));
}
}
while (!maskSK.empty()) {
calculateAndPutNumStack(maskSK, numSK);
}
return numSK.pop();
}
private void maskSKProcess(Stack<String> maskSK, Stack<Long> numSK,
String mask) {
if (maskSK.empty()) {
maskSK.push(mask);
} else {
Boolean is = isInStack(maskSK.lastElement(), mask);
if (is == null) {
maskSK.pop();
} else if (is) {
maskSK.push(mask);
} else {
calculateAndPutNumStack(maskSK, numSK);
maskSKProcess(maskSK, numSK, mask);
}
}
}
private void calculateAndPutNumStack(Stack<String> maskSK, Stack<Long> numSK) {
Long left = null;
Long right = null;
Long rs = null;
right = numSK.pop();
left = numSK.pop();
rs = calculate(maskSK.pop(), left, right);
numSK.push(rs);
}
// if in stack
public Boolean isInStack(String in, String out) {
int ing = getGrade(in);
int oug = getGrade(out);
ing = (ing == 8 ? 0 : ing);
return (ing == 0 && oug == 0) ? null : ing < oug;
}
private Long calculate(String mask, Long lm, Long rm) {
if ("+".equals(mask)) {
return lm + rm;
} else if ("-".equals(mask)) {
return lm - rm;
} else if ("*".equals(mask)) {
return lm * rm;
} else if ("^".equals(mask)) {
return pow(lm, rm);
}
return 0L;
}
private int getGrade(String mask) {
if ("(".equals(mask)) {
return 8;
}
if (")".equals(mask)) {
return 0;
}
if ("^".equals(mask)) {
return 6;
}
if ("*".equals(mask)) {
return 3;
}
if ("+".equals(mask) || "-".equals(mask)) {
return 1;
}
return -1;
}
private Boolean isMask(String str) {
return !str.matches("a|\\d+");
}
private Long pow(Long a, Long b) {
if (a == 1)
return 1L;
else if (b == 1)
return a;
else
return pow(a, b - 1) * a;
}
}
分享到:
相关推荐
noip2005普及组带数据1、陶陶摘苹果2、校门外的树3、采药4、循环
NOIP2013普及组复赛第二题《表达式求值》测试数据10组
noip2005试题!!!!!!!!!!!!!!!!!!!!!!!!!!!!
【noip2005普及】陶陶摘小苹果...............................................................................................................................................................................
noip全国青少年信息学奥赛提高组pascal语言,包含初赛、复赛试题、答案,测试数据,解题报告等。
NOIP2005第十一届普及组复赛.docx
整理了一下普及组的试卷,测试数据及题解。NOIP2005-2018年普及组复赛题目及完整测试数据,还有部分解题报告,附赠cena测评软件。
洛谷 P1046 [NOIP2005 普及组] 陶陶摘苹果 题解 简单易懂,欢迎查看!
2005年信息学奥赛NOIP普及组初赛试题及参考答案(完整版) 在此推荐给小伙伴们学习,希望对大家学习信息学有所帮助
可以大大方便搞OI的同学了。 使用方法,使用cena新建竞赛,将目录设为该文件夹,继续即可。
每天一道洛谷题P1048 [NOIP2005 普及组] 采药 这篇文章适合c++初学者。 愿每一位程序员少走弯路是我创作的初心,每篇博客都是用心输出,希望能够得到您的认可! 链接:...
学习编程需要用的,专门对于pascal语言来运用的,对于初中生来说是个不错的资料。
共享的noip2012年的初赛的题目,本不想设置积分的,但是看来最少是1啊!
NOIP2016普及组与提高组试题:NOIP2016复赛普及组试题&NOIP2016复赛提高组试题
NOIP
NOIP试题的解答!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
。。。
NOIP2012复赛数据 含:NOIP2012复赛普及组测试数据、NOIP2012复赛提高组测试数据
包含以下试题 1、明明的随机数(NOIP2006p1) 2、陶陶摘苹果(NOIP2005p1) 3、校门外的树(NOIP2005p2) 4、不高兴的津津(NOIP2004p1) 5、谁拿了最多奖学金(NOIP2005t1) 6、津津的储蓄计划(NOIP2004t1)