`

用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:

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 ...

 

分享到:
评论
3 楼 meiowei 2010-09-15  
yangguo 写道
i don't think it is a good way to solve this problem. you make the easy problem complex.

reason?  method?
2 楼 yangguo 2010-09-14  
i don't think it is a good way to solve this problem. you make the easy problem complex.
1 楼 jiajw0426 2009-06-11  
不错!!!

相关推荐

    java 拿火柴游戏

    Java 拿火柴游戏实验报告 一、 程序功能介绍 拿火柴游戏是一种与计算机相互对拿火柴的游戏程序,旨在训练人脑的逻辑思维能力。游戏的玩法是用系统产生的随机函数产生火柴数量(大约在 20—50 之间),每次每一方...

    java火柴游戏设计

    通过以上步骤,我们可以成功地用Java实现一个火柴游戏。这个过程不仅可以提升编程技能,也能锻炼逻辑思维和问题解决能力。无论你是初学者还是有一定经验的开发者,这样的课程设计都能提供宝贵的实践机会。

    用java编写的火柴游戏

    首先,游戏的核心是使用Java的`Math.random()`函数来生成随机的火柴数量。`Math.random()`函数返回一个0.0到1.0之间的随机浮点数,通过乘以(50-20)并加上20,可以得到20到50之间的随机整数,代表火柴堆的初始数量。...

    java课程设计-拿火柴游戏

    Java课程设计是一个重要的实践环节,旨在让学生通过实际编程项目来巩固和深化理论知识。在这个“拿火柴游戏”项目中,我们将深入...通过这个项目,学生不仅可以加深对Java语言的理解,还能提高实际编程和问题解决能力。

    移动火柴游戏

    在这款基于C++Builder开发的小游戏中,玩家需要通过移动火柴棍来解决一系列的谜题,目标是达到预设的目标形状或数字组合。游戏的核心在于观察、分析和创新,激发玩家的空间想象能力和逻辑推理能力。 C++Builder是一...

    JAVA拿火柴小游戏

    JAVA拿火柴的小游戏,使用JDK编写,JAVA初学者的范例程序,有出错循环,

    移动一根火柴使等式成立js版本

    这种类型的问题不仅考验逻辑思维能力,还能培养解决问题的能力。 ### 实现思路 该程序的主要实现思路可以概括为以下几点: 1. **定义数字变化规则**:首先定义了每个数字在添加、移动或减少一根火柴棍后可能变成的...

    用JAVA设计的火柴游戏

    次程序是用JAVA编写的火柴游戏。电脑有一定的智能。

    小学一年级下奥数专题—移火柴棒-一年级火柴棍.docx

    例如,在第一个问题中,要求用12根火柴棒组成4个正方形,通过移动3根火柴棒变成3个正方形。这是一个典型的图形变换问题,需要孩子们观察并思考如何通过移动火柴棒来减少正方形的数量。 第二个问题涉及等式的平衡,...

    移动一根火柴令等式成立(递归)

    ### 移动一根火柴令等式成立(递归)详解 #### 一、问题背景与目标 在解决“移动一根火柴令等式成立”的...这种方法不仅能够处理简单的等式变换,还能够应对更复杂的情况,为解决问题提供了一种灵活而强大的工具。

    巧移火柴棒练习题 (二年级)-二年级数学小棒题.docx

    巧移火柴棒是一种经典的数学智力游戏,适合于低年级学生锻炼思维灵活性和逻辑推理能力。...通过这些题目,孩子们能够更好地理解数字的结构、运算规则以及图形的变化规律,同时培养了解决问题的策略和技巧。

    java小程序 数火柴游戏 图形界面

    这是一个使用Java Swing框架开发的简单数火柴游戏。游戏的目标是通过移除一定数量的火柴来击败对手。游戏采用图形用户界面(GUI),使得玩家能够直观地看到当前游戏的状态,并进行操作。 ### 二、主要类和组件介绍 #...

    人机拿火柴游戏java代码

    人机对拿火柴的游戏程序 游戏过程要显示火柴总数 选择谁先拿

    JAVA课程设计合集!!!大学课程。贪吃蛇,21点,火柴人,俄罗斯方块,拼图游戏等多款课程设计游戏!

    Java课程设计是大学计算机科学教育中的重要组成部分,它旨在帮助学生深入理解面向对象编程思想,增强实际编程能力和软件...如果你在使用过程中遇到任何问题,记得寻求帮助,共同探讨和解决问题是学习过程中的重要环节。

    还记得:移动其中一根火柴使等式成立的趣味游戏吗?

    2. **图形界面**:Unity3D的图形渲染能力可以创建逼真的3D火柴模型,用户可以通过点击或拖动来模拟移动火柴的动作。 3. **用户交互**:C#脚本会处理用户的输入,判断移动是否合法,以及是否解决了当前的谜题。 4. ...

    巧移火柴棒练习题集(二年级)~二年级数学小棒题.doc

    巧移火柴棒是一种锻炼逻辑思维和数学技巧的趣味题型,主要针对低年级学生,旨在提高他们的数学理解和创新思维。...通过解决这类问题,孩子们不仅可以提升数学技能,还能培养解决问题的策略和思维方式。

    基于JAVA实现的控制台火柴棍游戏

    【作品名称】:基于JAVA实现的控制台火柴棍游戏 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】:项目简介 Match-game...

    巧移火柴棒教学设计.docx

    6.思考题:通过移动火柴棒,学生可以学习解决问题的方法和策略。 四、教学目标 * 培养学生动手能力和空间想象能力 * 通过火柴棒摆出数字图形和巧移火柴棒等活动,提高学生的逻辑思维和问题解决能力 * 培养学生的...

    我的火柴人RPG游戏,使用Java语言开发,利用awt作为图形引擎,引用Minecraft素材包,开发的2D游戏。.zip

    《我的火柴人RPG游戏》是一款基于Java编程语言,运用AWT图形库构建的2D角色扮演游戏。这款作品巧妙地融入了Minecraft的游戏元素,为玩家提供了独特的游戏体验。作为一个学习与实践的项目,它适合用作毕业设计、课程...

    巧移火柴棒游戏训练方法及训练题库.docx

    本篇文章将详细介绍巧移火柴棒游戏的训练方法,并深入探讨训练题库的运用,旨在帮助玩家在娱乐中提高他们的思维灵活性和解决问题的技巧。 ### 巧移火柴棒游戏的训练方法 #### 第一阶段:入门练习 初学者首先需要...

Global site tag (gtag.js) - Google Analytics