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 expression into three categories of simple expressions. 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 [] Array for various arrangements * / / * c [] Store four cards * / / * k [] C [] The code of four cards, where K [I] = i 1. Use it instead of C [] to do, considering the case of the same number in C [] * / / * kans [] Specifier Brand Brand * / / * 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 IF (k [p]! = kans [r]) FLAG ; if (flag == j) T [J] [q ] = k [p];} for (s [j] = 0; s [j] <4-j; s [j] ) {kans [ J] = T [j]; if (j == 3) {for (h = 0; h <4; h ) ANS [2 * h] = C [kans [h] -1] ; / * Adjust the generated arrangement in the final expression * / for (h = 0; h <3; h ) Symbol (ANS, H); / * Add an operation symbol * /} else in the expression {J ; Fans (C, K, ANS, KANS, J); J-;}}}
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 = 2) for (n = m 4; n <= 8; n = 2) This FOR loop gives 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 OVS 3, and continue to scan the next character 4, if W is the operator 5, according to the nature of the operator, the corresponding processing: (1), if the operator is the priority of the left parentheses or operator, the priority is greater than the operator stack The operator (ie, OPS (TOP)) is pressed into the operator W. The operator W is pressed 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, and then convert the linear expression into a machine instruction sequence for evaluation.
So what is the linearization of expressions? The expression method of the expression of people habits is called prefix. The prefix indication is that the operator is located in the middle of the operation object. But this means, sometimes it must be clearly expressed in the order of operation, and the processing is more complicated.
In 1929, Poland LUKASIEWICZ proposed a logical symbol system that does not have to be brackets, which later called Polish NOTATION. The Poland Expression is characterized by the operator behind the operation object, so it is called a suffix representation. The polish expression is calculated, which is strictly in 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 into 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 for conversion and calculation is given below
/ * The first function 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 influented to the suffix * / / * m value macro is defined as 20 * / / * sp [] is an expression array * / int mid_last () {INT i = 0, J = 0; CHAR C, SM [M]; C = S [0]; SM [0] = '='; TOP = 0; While (C! = ') {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] = ''; return (0);} / * is calculated by the suffix expression * / int Calc () {INT i = 0 , SM [M], Tr; CHAR C; C = SP [0]; TOP = -1; While (C! = ') {IF (Islower (C)) SM [ TOP] = Ver [C- 'a']; / * Instead of using ABCD during the conversion process, it can be more convenient to handle non-one, and the number of these letters replaced in the VER array * / 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 solves, go back to take This program is counted as the problem starting with the article. Haha, it is calculated, it is so simple - (6-3) * 10-6 = 24.
Finally, I summed up this way that is prone to error --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.
2, when applying the nested function, you need to analyze the execution process of the program, and make appropriate adjustments for individual variables (such as the value of J), the program can perform correctly.
3. When analyzing parentheses problems, don't miss any possible opportunities, and try to make programs simple. But my analysis may have problems, please also give your guidance.
4. When using a function to handle one array, be sure that if this array also needs to be applied, you must save it first, otherwise it will be wrong, and it is very serious.
5, when processing the expression of the user input, since a ten digit or higher number is decomposed into a number of digits in an array, they need to be processed, and they are converted into actual integer variables. In addition, in the conversion process, use a letter instead of this number and exist in an array, and it has certain contacts in the array and this letter instead of it, so that this number can be retrieved.
6. Since there is a calculation of 0 calculations in the calculation process in the calculation process, we must handle the CALC functions for additional operations, otherwise it will exit because of an error (Divide By 0).
7. The last issue, this program has not been resolved. This program cannot answer for some more famous topics. For example, 5, 5, 5, 1 or 8, 8, 3, 3. This is because these topics are used in the calculated process, and this program does not take into account the decimal.
