"Magical 24" game refers to four ABCDs and - * / (), solving an arithmetic method such that the assembly of the equation is 24. When I was a child, I have played like this, it is on the computer. Now I think about it is not difficult to achieve it.
The first thing I think is of course means using the powerful calculation capacity of the computer, and I will exhaust each possible expression. It is determined that the result is 24, and the expression of the result is 24 directly output directly. Among them, it is related to the generation and solving expression.
The method of solving the expression, in the data structure, a method of solving the expression, the descending method of the suffix expression. The suffix expression is most convenient for this problem, and its advantages will be seen later. The suffix expression is very simple: the composite representation is scanned by left to right, and the following rules are applied to each element of the equation: 1. If the element is a variable or operand, press it into the stack; 2. If the element is an operator, two elements of the top of the stack are popped, complete the operation, and press the result into the stack; 2. After the entire expression is scanned, the expression results are saved on top of the stack.
A method of infix expression of a blotting expression: This algorithm is attributed to Dijkstra. Scanned from left to right, with the scan, the suffix expression is generated and output, the steps are as follows: 1. Check the next element of the input. 2. If it is an operand, it outputs it. 3. If it is a knot (left bracket), press it into the stack. 4. If it is an operator, if the top of the stack is a knocked bracket, press the operator into the stack. If it has higher priority than the top operator (multiplication and additional priority to the addition), the operator is pressed into the stack, otherwise the operator is detected from the stack to the output, and step 4 is repeated. 5. If it is a close bracket (right bracket), the operator pops up to the output until it encounters a parenthesis, and the scrap will be popped up. 6. If there is an input, return to step 1. 7. If no input is input, all remaining operators are popped up.
Why use suffix expressions? This will look at the expression generation method. If you use a prefix expression, it is rare to the generation of expressions, because it involves processing of parentheses, think about it, you will know how much it is difficult. With the suffix expression, there is no need to handle parentheses, and we can also analyze how many possible expressions in all possible expressions, and what forms are now analyzed:
For the four numbers of ABCD, the position of each number is first fixed, this is the requirements of the game rules, this is greatly reduced to our solution, think about if the number of position is not fixed, the number of searches will be It is the class of the current 4. It can be said that the order of its operands is also not changed, which is guaranteed by the order of the operand. Another important point is that in a legal suffix expression, any of the operators, the number of operators in front of it, always has the number of operands in front of it. The following relationship: Operations number Legal suffix: ABCD - * illegal suffix type: A BCD - ( one operand in front 1 <1 is not established) Now see how to construct these reasonable expressions, obviously reasonable forms can only have the following form: 1. AB * C * D * 2. AB * CD ** 3. ABC * D ** 4. ABC * * D * 5. ABCD *** Among them, * represents any operator in the addition and subtraction, for each form, there are 4 * 4 * 4 = 64 expressions, there are 5 forms, all expressions There are 64 * 5 = 320, that is, only 320 sponses. In this way, we found all possible methods of constructive, and after constructing all the forms, we use the suffix expression to solve the solution, solve each of the formats and determine whether or not it is equal to 24. What is left is how to turn the suffix expression into a prefix form and output, this is not difficult, refer to the solve method of the suffix expression, you can know that it is not asked when you encounter an operator. And directly generate a string, press the stack. The specific implementation has not been written yet. Today can only talk about the implementation of the realization I imagined, and everyone will not joke. Author: Chen Kai RockCarry studio: http: //rockcarry.126.com 2005.1.7 All Rights Reserved
