- 浏览: 75951 次
文章分类
最新评论
-
wodentt:
....为什么楼主都英文的博客
用java解决百度之星移动火柴的问题 part 1 -
wensonzhou86:
思路明确,代码清晰,通俗易懂
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
carydeepbreathing:
代码比较干净
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
meiowei:
yangguo 写道i don't think it is a ...
用java解决百度之星移动火柴的问题 part 2 -
yangguo:
i don't think it is a good way ...
用java解决百度之星移动火柴的问题 part 2
The next task is to evaluate a given expression. A simple way is to build a generic evaluator for the simple math expression we are dealing with. In fact, building a parser for +, -, /, * and ^(for powers) is as much work as building one for just + and -. The references we are using here are:
- http://www.smccd.net/accounts/hasson/C++2Notes/ArithmeticParsing.html
- http://www.chris-j.co.uk/parsing.php
There are tons of references on the language parsing, but these are enough for us to build a simple one. Again, the code is under 200 lines.
import java.util.List; import java.util.ArrayList; import java.util.StringTokenizer; import java.util.Stack; import java.util.Queue; import java.util.LinkedList; public class NumericExprParser { public double evaluate(String expr) { Queue<String> postFixExpr = convertToPostFixExpr(expr); return evaluatePostFixExpr(postFixExpr); } private double evaluatePostFixExpr(Queue<String> queue) { Stack<Double> stack = new Stack<Double>(); while (!queue.isEmpty()) { String t = queue.remove(); if (isNumber(t)) { stack.push(Double.parseDouble(t)); } else if (isOperator(t)) { Double n1 = stack.pop(); Double n2 = stack.pop(); // for unary operators, this is empty. if (t.equals("+")) stack.push(n2 + n1); else if (t.equals("-")) stack.push(n2 - n1); else if (t.equals("*")) stack.push(n2 * n1); else if (t.equals("/")) stack.push(n2 / n1); else if (t.equals("^")) stack.push(Math.pow(n2, n1)); } } return stack.pop(); } private Queue<String> convertToPostFixExpr(String expr) { Queue<String> queue = new LinkedList<String>(); Stack<String> stack = new Stack<String>(); String[] tokens = getTokens(expr); for (String s : tokens) { if (isNumber(s)) { queue.add(s); } else if (isOperator(s)) { while (!stack.isEmpty() && isOperator(stack.peek()) && isSameOrHigherPriority(stack.peek(), s)) { String t = stack.pop(); queue.add(t); } stack.push(s); } else if (s.equals("(")) { stack.push(s); } else if (s.equals(")")) { String t; while (!(t = stack.pop()).equals("(")) { queue.add(t); } } } while (!stack.isEmpty()) { String t = stack.pop(); queue.add(t); } return queue; } private boolean isNumber(String s) { try { Double.parseDouble(s); return true; } catch (Exception ex) { return false; } } private boolean isOperator(String s) { return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("^"); } private boolean isSameOrHigherPriority(String s, String t) { if (t.equals("+") || t.equals("-")) { return true; } else if (t.equals("*") || t.equals("/")) { return s.equals("*") || s.equals("/") || s.equals("^"); } else if (t.equals("^")) { return s.equals("^"); } else return false; } private String[] getTokens(String expr) { List<String> tokens = new ArrayList<String>(); StringTokenizer st = new StringTokenizer(expr, "+-*/^()", true); while (st.hasMoreTokens()) { String s = st.nextToken().trim(); if (!s.equals("")) { tokens.add(s); } } return tokens.toArray(new String[0]); } }
This parser can handle +, -, /, *, ^ and (). Since we don't need unary -, it's not there. The parentheses is for () only, since we don't need [] and {}.
This class is sufficient for our purpose. A test case is like this:
import junit.framework.TestCase; public class NumericExprParserTest extends TestCase { private NumericExprParser exprParser = new NumericExprParser(); public void testEvaluate() { String expr = "(10 - 1) * 2 / 3 ^ 2"; double res = exprParser.evaluate(expr); System.out.println(res); assertTrue(res == 2); expr = "2 * 3 + 5 * 4 / 2^2"; res = exprParser.evaluate(expr); System.out.println(res); assertTrue(res == 11); expr = "0 -5 * 3^2"; res = exprParser.evaluate(expr); System.out.println(res); assertTrue(res == -45); } }
Note that this class is a reusable class, not just for our problem here.
With these building blocks, we are ready to attack the problem. There are several steps:
- We need to check whether the original one is already a solution, such as 1 + 1 = 2. This is because once we take a match off and it's not a number anymore, then we lose this solution. Otherwise, we just loop through all possibilities and disgard any case where we can't form numbers.
- Given a string, we convert the digits into MatchDigit AND we keep a reference from MatchDigit to the original digit so that once we have a new expression in matches, we can convert them back to strings in order to use the evaluator to evaluate.
- Once we have the MatchDigit list, we can loop through all possibilities to find the solutions. In here, I just print out the solutions. A better way would be to construct some kind of result class to return the results, but I leave that out for simplicity without much harm.
The class is as follows:
import java.util.ArrayList; import java.util.HashMap; /** * Given an arithmetic expression, by moving one match to make it a valid equation. */ public class MatchDigitEquatorSolver { private static final String DIGITS = "0123456789"; public void solve(String expr) { // check the original expression if (checkResult(expr)) { System.out.println("The original expr is a solution: expr: " + expr); } HashMap<MatchDigit, Integer> indices = new HashMap<MatchDigit, Integer>(); ArrayList<MatchDigit> mds = new ArrayList<MatchDigit>(); for (int i=0; i<expr.length(); i++) { char c = expr.charAt(i); if (isDigit(c)) { int digit = c - 48; MatchDigit md = new MatchDigit(digit); mds.add(md); indices.put(md, i); } } for (MatchDigit md : mds) // loop through all digits { for (MatchPosition mp : md.getAllMatches()) // for each digit, loop through all matches { MatchDigit newMd = md.takeMatch(mp); if (newMd == null) continue; // meaning this is not a valid digit once we remove the match. // now we have a new digit, we need to put the match somewhere for (MatchDigit md1 : mds) // loop through all digits again to see whether we can put the match somewhere. { for (MatchPosition position : MatchPosition.values()) { MatchDigit newMd1 = md1.setMatch(position); if (newMd1 == null) continue; // now we have a valid new digit, we need to check the result. // replace the old digits with the new one. String newExpr = expr.substring(0, indices.get(md)) + newMd.value() + expr.substring(indices.get(md)+1); newExpr = newExpr.substring(0, indices.get(md1)) + newMd1.value() + newExpr.substring(indices.get(md1)+1); if (checkResult(newExpr)) { System.out.println("expr: " + expr); System.out.println("new expr: " + newExpr); System.out.println("move match " + mp + " from digit[index: " + indices.get(md) + "] " + md.value() + " to the position " + position + " in the digit[index: " + indices.get(md1) + "] " + md1.value() + "."); } } } } } } private boolean isDigit(char c) { return DIGITS.indexOf(c) > -1; } private boolean checkResult(String expr) { String[] exprs = expr.split("="); NumericExprParser parser = new NumericExprParser(); double left = parser.evaluate(exprs[0]); double right = parser.evaluate(exprs[1]); return left == right; } }
Although there are still 4 for loops, they are more managable in the context as they are close to the pseudo code we present at the beginning, i.e., they are aligned with the business logic. A test case is like this:
import junit.framework.TestCase; public class MatchDigitEquatorSolverTest extends TestCase { private MatchDigitEquatorSolver solver = new MatchDigitEquatorSolver(); public void testSimple() { String a = "9 + 5 = 9"; solver.solve(a); } public void testOriginal() { String a = "4 + 5 = 9"; solver.solve(a); } public void testMoreDigits() { String a = "19 + 5 = 19"; solver.solve(a); } public void testParen() { String a = "2 * (9 + 5) = 18"; solver.solve(a); } }
Note that in our code there is no restriction to single digit number, as shown in the 3rd case in the above. And we allow ^(power) operators as well.
The results are like this:
expr: 9 + 5 = 9 new expr: 3 + 6 = 9 move match UPPERLEFT from digit[index: 0] 9 to the position LOWERLEFT in the digit[index: 4] 5. expr: 9 + 5 = 9 new expr: 3 + 5 = 8 move match UPPERLEFT from digit[index: 0] 9 to the position LOWERLEFT in the digit[index: 8] 9. The original expr is a solution: expr: 4 + 5 = 9 expr: 19 + 5 = 19 new expr: 13 + 6 = 19 move match UPPERLEFT from digit[index: 1] 9 to the position LOWERLEFT in the digit[index: 5] 5. expr: 19 + 5 = 19 new expr: 13 + 5 = 18 move match UPPERLEFT from digit[index: 1] 9 to the position LOWERLEFT in the digit[index: 10] 9. expr: 2 * (9 + 5) = 18 new expr: 2 * (3 + 6) = 18 move match UPPERLEFT from digit[index: 5] 9 to the position LOWERLEFT in the digit[index: 9] 5.
Now we are done, like we do college homework(meaning we throw them away once we get the grades). But as professional software engineers, we always wonder what's next because we need to maintain "the damn thing". What if we change our requirement, say, we can now move two matches? Or allow more operations. How flexible is our class structure to handle these changes? In the first case, we just need to write a new solver class and reuse the MatchDigit and parser classes. In the second case, we just modify the parser class or write a completely new one.
Normally, a stateless operation has less entanglement than stateful operations. For example, writing a parser for, say java, language is much harder than this example because parsing tokens heavily depends on the token series and the current position in the series, e.g., the parentheses handling, the math functions and their arguments handling.
Think, think, think ...
评论
reason? method?
发表评论
-
Spreadsheet Dependency graph
2010-11-19 03:00 2040In spreadsheets, such as Excel, ... -
Composition
2010-07-03 03:56 0I saw a post in the forum some ... -
Revisit again: 一道应聘智力题的编程求解, Einstein puzzle
2010-06-30 04:30 1566Continue on: http://jellyfish.i ... -
Domain Driven Design
2010-01-16 02:42 1175Having read a lot of discussion ... -
用java解决百度之星移动火柴的问题 part 1
2009-06-09 02:24 1902Recently, I saw a post: htt ... -
CEP
2007-07-11 02:54 1209http://www.eventstreamprocessin ...
相关推荐
JAVA拿火柴的小游戏,使用JDK编写,JAVA初学者的范例程序,有出错循环,
java 拿火柴游戏实验报告 里面含有源代码,可以运行,希望对您有所帮助
用C语言写的算法,四位数火柴棍移动其中一根变四位最大数。
次程序是用JAVA编写的火柴游戏。电脑有一定的智能。
这个小游戏是用java编写的,就是让电脑ramdom选择火柴根数,然后用户选择根数。
学校java课程设计做的数火柴小游戏的源代码 每行都有注释
程序随机产生20—50根火柴,由人与计算机轮流拿,每次拿的数量不超过3根,拿到最后一根为胜
人机对拿火柴的游戏程序 游戏过程要显示火柴总数 选择谁先拿
基于c++Bulider做的一款小游戏,移动火柴棍游戏,含整个工程文件
移动一根火柴使等式成立js版本
java编写的一个小游戏,可以用来当做java课程设计。
Swing Star 摇摆之星 Unity火柴人横版跳跃抓绳闯关项目源码C# 支持Unity版本2018.2.6f1及以上 描述 准备在 Android 和 iOS 上发布 摇摆之星来了! 捕捉、摆动、滑行,享受。 各种皮肤和主题。 特征 易于重新换肤 令...
移动一根火柴令等式成立(递归)
近日空虚,用java编写了一个火柴棍的小游戏。还是练练手。其中使用线程有些要改进,也想好了点,但现在很懒,不想写。例如线程中可以使用wait()方法,但本人没有用,这点可以加以改进。还有许多类似的情况。能力...
良心出品!...大学JAVA课程设计合集。这里有你想要的课程设计系统。亲测全部调试运行成功,有需要的下载吧! 压缩包包括:贪吃蛇,21点,火柴人,俄罗斯方块,拼图游戏等多款课程设计游戏!如有问题,请联系
利用U3d写的 移动其中一根火柴使等式成立的趣味游戏 源码
火柴人java源码火柴人游戏 介绍 一个用 Java 编写的关于角色的 2D 平台游戏:火柴人。 扮演火柴人,打败敌人并在穿越不同级别直到达到最终目标的同时获得能量提升。 程序运行说明: 转到您的终端并输入程序的路径,...
用java写的项目,免费分享给大家,比较适合新手入门学习,欢迎下载使用。用java写的项目,免费分享给大家,比较适合新手入门学习,欢迎下载使用。用java写的项目,免费分享给大家,比较适合新手入门学习,欢迎下载...
flash as2.0制作的小游戏智力移动火柴
火柴人java源码 ## PhalApi,简称π框架,是一个PHP轻量级开源接口框架,专注于接口开发,致力让接口开发更简单。它: 致力于快速、稳定、持续交付有价值的接口服务 关注于测试驱动开发、领域驱动设计、极限编程、...