Long holiday is always boring for me, and I am bored with my classmates to play twenty-four cards that often play with childhood. This game is simple, that is, using the addition and subtraction and division and the brackets, the four cards given into a value of 24 have a expression of 24. But there is no lack of interesting topics, this is not, we have just played a while, I have encountered a problem - 3, 6, 6, 10 (in fact, think about it, this is not a difficult question, just at the time Our brains have not turned, huh, huh).
Since the question appears, we certainly want to solve it. On the occasion of meditation, my mind has passed a thought - why not compiled a program to solve this problem? Is there such a program in Wencheng? So this idea should be feasible. I thought that I immediately started thinking about this program, the first thing I thought was the ill, (later found that I can't think of a better way again, sad, huh, sorrow, huh, huh), because I have written a small program in this semester - Calculate simple expressions with parentheses. As long as I can program the exhaustion of the expressions constituted by the four numbers, don't you use this computing program to complete this calculation of twenty four points? After the idea, I started to think about the details of this problem.
First, feasibility problems that are exhaustive. I divide the expressions into three categories -
1. Simple expression of hazardous numbers. 2, there is a simple expression of parentheses. 3, there are two brackets of more than 4, miscellaneous forms. The start of exhaustion, I am arranged to give the four numbers, which may be 4 * 3 * 2 * 1 = 24. I use a nested function to implement four numbers, the algorithm is as follows:
/ * ANS [] used to store various arranging combinations of array * // * c [] stored four cards * // * K [] C [] Type four card code, where K [i] = I 1. Use it instead of C [] to do handle, considering the case of the same number in C [] * // * kans [] Specifier group * // * j Necrinks * / int fans (C, K, ANS, Kans, J) Int J, K [], C []; CHAR ANS [], Kans []; {INT I, P, Q, R, H, Flag, S [4], T [4] [4]; for (p = 0, q = 0; P <4; p ) {for (r = 0, flag = 0; R As mentioned above, after completing the arranging of the four cards, add an operation symbol in the expression. Since there is only four cards, just add three arithmetic symbols. Since each arithmetic symbol can be repeated, it calculates its possible number of 4 * 4 * 4 = 64. Still use the nested function to achieve the exhaustion of the integrated symbol, the algorithm is as follows: / * ANS [], J. SY [] Store four arithmetic symbols. H is an expression form. * / int SANS (ANS, SY, J, H) CHAR ANS [], Sy []; Int J, H; {INT I, P, K [3], M, N; Char Ktans [20]; for ( K [J] = 0; K [J] <4; K [J] ) {ANS [2 * J 1] = SY [K [J]]; / * The four numbers just stored in 0 , 2, 4, 6 the three arithmeters here are stored in 1, 3, 5-bit * / if (j == 2) {ANS [5] = SY [K [J]]; / * This Different expressions are processed in the form of corresponding processing * /} else {J ; SANS (ANS, SY, J -, H);}}} is ok, then I will consider processing of different expressions. Just now I have divided the expression into three categories, because the addition of three braces are definitely repetitive for four cards. For the first one, there is no need to be proactive; in the second case, there is six kinds of the following code, and one is excessive. FOR (m = 0; m <= 4; m = 2) For (n = m 4; n <= 8; n = 2) This FOR cycle gives the number of possibilities of the possibility of adding a parentheses, where M, N is the position of the left and right parentheses added in the expression. What I said is that M = 0, n = 8, that is, on both ends of the expression. This is really more, huh, huh! The last situation is to add two parentheses, I analyzed it, I found that this form is not repeated - (A b) (C D). Why not appear in nesting brackets? Because if it is nesting bracket, the outer parentheses is definitely containing three numbers (four unnecessary), that is, this bracket contains two arithmetic symbols, and the two arithmetic symbols are separated by another bracket. It's open. Then, if the two arithmetic symbols are the same priority, they must definitely go to the parentheses through some conversion (you may wish to give some examples to try), that is, this parentheses is not necessary; if these two arithmetic symbols are not the same priority Level, it is inevitably this form ((A -B) * / c). And * and / in these arithmetic symbols are the highest, naturally there is no need to add parentheses in its outside. In summary, all possible expressions are 24 * 64 * (1 6 1) = 12288. Haha, there are only more than 10,000 possibilities (this also has repeat), this is a small case! Therefore, it is done for feasibility analysis and implementation of exhaustion. The next question is how to process the simple expression of the symbol. This is a famous application of the stack, then what is the stack? The concept of stack is abstract from the access process of goods in the daily life, that is, the last stored goods (the stack is in the exit) first extracted, in line with "advanced, afterwards, the first out" in principle. This structure is like a bullet holder. In the stack, the insertion of the element is referred to as pressing (PUSH) or the stack, and the deletion of the element is referred to as a pop-up (POP) or a decor. There are three basic operations of the stack, including the stack operation, the decall operation, and the top elements of the watch, please refer to the relevant data structure. According to these basic operations, you can use the array to simulate the stack. So as the famous application of the stack, the calculation of the expression can have two methods. The first method - first build two stacks, operate a stack OVS and operator stack OPS. Among them, the operator stack is used to memory the operand in the expression, and the top pointer is TOPV, which is empty, ie TOPV = 0; the operator stack is used to memory the operator in the expression, and the top pointer is Topp, initially, there is only one expression end in the stack, namely TOPP = 1, and OPS (1) = ';'. The ';', the expression end of the expression. Then the expression to be processed from left to right, and assumes that the current scanned symbol is W, according to different symbol W Different processing: 1, if W is an operand 2, the W is pressed into the operand Stack OVS3, and continue to scan the next character 4, if W is the operator 5, according to the nature of the operator: (1), if the operator is the priority of the left bracket or operator, the priority is greater than the operator stack The top operator (ie OPS (TOP)), press the operator W into the operator stack OPS and continues to scan the next character. (2) If the operator W is the expression end value ';' and the operator of the operator stack stack is also the expression end value (ie OPS (TOPP) = ';'), the processing process ends, at this time , Operate a stack stack top element (i.e., OVS (TOPV)) is the value of an expression. (3) If the operator W is the right bracket and the operator of the operator stack stack is the left bracket (ie OPS (TOPP) = '('), the left brackets are discussed from the operator stack and continue to scan. A symbol. (4) If the operator is not greater than the operator (ie OPS (TOPP)) of the operator stack stack, two operands are populated from the operation count stack OVS, and the number of operands that have been popped up is A, B, and then pop up an operator from the operator stack OPS, set to , then operate A B, and press the calculation result into the operator counting OVS. The operator will be re-considered next time. Two methods - First, linearize the expression, then convert the linear expression into a machine instruction sequence for evaluation. What is the linearization of the expression? The expression method of the expression of people habits is called The prefix representation is characterized by the integrator. The operator is located in the middle of the operation object. But this representation is sometimes necessary to express the order of operations in order, and the processing is more complicated. In 1929, Poland Luster Lukasiewicz proposed The logical symbol system that does not have to be brackets later, it is called Polish Notation. The Poland Expression is characterized by the operator behind the operation object, and therefore referred to as a suffix. Conducting the Polish expression, strict According to the order from left to right. Some expressions and their corresponding Polish expressions are given below. Expression Polish Expression AB AB- (AB) * C D AB-C * D A * (B C / D) -e * f Abcd / * EF * - (B C) / (AD) BC AD- / OK, the linearization of the so-called expression refers to the expression of expressed expression to a Polish expression. For each expression, the use of the stack can transform the expression into a polish expression, or the value of the Polish expression can also be calculated using the stack. As for the process of conversion and calculation and the first method, it will not be described here. The specific implementation program - / * first function of the conversion and calculation is given below gives the priority of each operator, where = an expression end value * / int first (CHAR C) {INT P; Switch (C) {CASE '*': p = 2; Break; Case '/': P = 2; Break; Case ' ': P = 1; Break; Case '-': P = 1; Break; Case '(': p = 0; Break; Case '=': P = -1; Break;} return (p);} / * This function is infixed to the suffix of the transition * // * m value macro is defined as 20 * // * SP [] For the expression array * / int MID_LAST () {INT i = 0, J = 0; CHAR C, SM [M]; C = S [0]; SM [0] = '='; TOP = 0; While (C! = '/ 0') {IF (Islower (C)) SP [J ] = C; Else Switch (c) {CASE ' ': Case '-': Case '*': Case '/' : while (first (c) <= first (sm [TOP])) SP [J ] = SM [Top -]; SM [ TOP] = C; Break; Case '(': SM [ TOP ] = C; Break; Case ')': while (sm [TOP]! = '(') sp [j ] = SM [Top -]; top ---; break; default: return (1);} C = S [ i];} while (TOP> 0) SP [J ] = SM [TOP -]; SP [J] = '/ 0'; return (0);} / * By suffix expressions Calculate the value of the expression * / int Calc () {INT i = 0, SM [M], Tr; CHAR C; C = SP [0]; TOP = -1; While (C! = '/ 0') { IF (Islower (C)) SM [ TOP] = VER [C-'A ']; / * Instead of using ABCD during the conversion process, this can be more convenient to handle non-one, VER array Mids the number of these letters instead * / else switch (c) {case ' ': Tr = SM [TOP ---]; SM [TOP] = Tr; Break; Case '-': Tr = SM [ TOP ---]; SM [TOP] - = Tr; Break; Case '*': Tr = SM [TOP -]; SM [TOP] * = TR; Break; Case '/': Tr = SM [TOP -]; SM [TOP] / = Tr; Break; default: return (1);} c = sp [ i];} if (TOP> 0) Return (1); Else {result = SM [Top]; Return (0);}} This program basically even solves, go back to take this program to count the problem starting with the article. Haha, it is calculated, it is so simple - (6-3) * 10-6 = 24. Finally, I summed out this that is prone to mistakes - 1, when the arrangement can only appear once, there must be a judgment statement. But what is used to judge, it is clear that the size is obvious, because there may be two or more numbers in these four numbers. My method is to set a code for each number, and find this number through this code at the end of the alignment.
