For the calculator, there are many mature theories. This article discusses a method of calculating an operand stack and an operator stack. This algorithm has a perfect solution that discusses the most simplified model here, which is designed to learn the essence of this algorithm in the shortest time, and can be flexibly applied to any area of scientific research.
Simple expression calculation
First of all, please see this expression: 3 5 6 * 7 * 8 ^ 2 ^ 3 (8 ^ 2 refers to 82) There are three priorities "^" -> "^" -> " " here. How to achieve priority Level calculation?
When the scan string 3 5 6 * 7 * 8 ^ 2 ^ 3.
1. First move into 3 5, and find that the next operator is , the priority is the same, so that 3 5 is calculated first, change them to 8. Then the formation becomes: 8 6 * 7 * 8 ^ 2 ^ 3 2. Now the next operator * priority is higher than the previous high, so continued to move: 8 6 * 7 * 8 ^ 2 ^ 3 3. Now An operator is *, which is the same as the previous one, so before calculating 6 * 7, the format becomes: 8 42 * 8 ^ 2 ^ 3 4. Continue: 8 42 * 8 ^ 2 ^ 3 5. 8 42 * 64 ^ 3 6. 8 42 * 262144 7.8 1.101 * 107 8.101 * 107
Now the seizure becomes a number, the entire calculation is over.
But how do I complete this process in my computer? When you encounter 8 6 * 7, you must follow 6 * 7, but where is 8 and ? The method used here is to create an operand stack and an operator stack, press 8 and to two stacks, respectively. For fashion: 3 5 6 * 7-8 ^ 2
Remaining child operand stack operator stack priority comparison operation 3 5 6 * 7-8 ^ 2 ± 6 * 7-8 ^ 2 3, 5 ± equal calculation 3 5 = 8 6 * 7-8 ^ 2 8 * 7-8 ^ 2 8, 6 ± 6 ± 8 ^ 2 8, 6, 7 , * less than calculation 6 * 7 = 42-8 ^ 2 8, 42 equal to calculation 8 42 = 50-8 ^ 2 50 ^ 2 50, 8 - greater than 50 , 8, 2 -, ^ calculation 8 ^ 2 = 64 50, 64 - Calculation 50-64 = -14 -14 ^ ----------------------- -------------------------------------------------- ------------------------------------- can be seen if the opera stack and operator stack If it is: 1. Step scan expression. 2. In the case of the operand, it is pressed into the operand stack. When the operator compares its priority and operator stack stack, if it is more priority, press it into the stack, Otherwise, the stack top operator pops up. As long as this can achieve a priority operation. Priority change
Three priorities are specified in my sample program
, -, self-reverse operation (-X, -Y, -Z, -1, -2): priority is 1 (lower) *, /: priority is 2 ^: priority is 3 (highest)
But "(" The priority should be, the bracket refers to the beginning of a new operation, for 3 5 * (6-2), when scanned "(", the original priority is all invalid, everything needs to be re- Calculate, therefore, "(", when scanning, 将 它 无 压 压 入 栈 栈 置 优 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 级 1. 1. "Tg (", "LG (", "ln (", etc. I encountered ")", I should not stop out to find "(" Sin ("," CoS (",", ". "Tg (", "LG (", "LN (", etc.. Process
For a legitimate simple mathematical expression, it is definitely an operand followed by an operator, the first and last one is an operand. Therefore, the simplest program writing method is to write a program ccalc :: getOperand (), and then write a program ccalc :: getoperator (), and then loop execution.
While (! getOperand () &&! getoperator () &&! verror);
This can calculate the final result.
1. Take the operating number getOperand (): (1) When you take the operating number, you will not necessarily be the operand itself, but may be "(", "sin (", "COS (", "(", "tg "," LG ("," or " " or meaningless " ", first pressing them into the operator stack. (2) Then check is "X", " Y "," z "and other variables or" pi "and other constants, and some of them press their value to the operator stack. (3) If it is not a variable or constant, the legality of the number of times is not the legal number, Exit all the operations.
2. Access operators getoperator (): (1) The first encounter when the operator is not necessarily an operator, but may be ")", first handle it. (2) Then check that it is the final resulting result if it is the final result. (3) Remove the new operator and give it the priority. (4) If the operator stack is not empty, pop up an operator, a priority, if the new operator priority is less than or equal to the pop-up operator priority, turn back the pop-up operator, otherwise the pop-up operator Computation. (5) Press the new operator into the stack.
