Remember before
The girl friend say: “high count good difficult, see me recently quite laborious, you send me a gift to me, let me happy once. Guess what I want.”
I thought about everything from books to shoes to electronics to groceries and said, “I’ll give her whatever you want.”
She insisted, “No, you have to say a gift, and you have to make it yourself.”
So, I got serious, picked up the phone, Taobao shopping for a few minutes, but still failed to come up with any shortcomings, finally there is no way: “Tell you what, if you really want me to send something, let me help you write a calculator.”
The title of the article is just a gimmick. As learners of communication technology, we should keep our feet on the ground, so I will make sure that the content of the article is authentic!
Design principle
According to the input infix arithmetic expression, the stack frame structure is used to convert the output into postfix expression, and then evaluate the postfix expression to calculate the output result. The result was a calculator.
Range: + – * / % Integer decimal negative number
Design idea
Logic design
- Create two stacks, stack and stack Node
- The stack is used to store character arrays, which store the elements of infix expressions as characters.
- The Node stack is used to store double-precision floating-point arrays that store the element values of infix expressions and the values after each element operation.
- Design the following two functions and the corresponding on – and off-stack operations.
| The function name | parameter | role |
|---|---|---|
| Mtf_function() | char *p1,char *mid,char *final | Used as an infix to a suffix |
| Caculate() | stack *M,char *final | Evaluates postfix expression values |
Mtf_function() function design
(Stack is stack)
(1) If an operand is encountered, print it directly.
(2) If we encounter an operator, we put it on the stack, and when we encounter an open parenthesis, we put it on the stack.
(3) If a close parenthesis is encountered, the stack element is ejected, and the pop-up operator is printed until the open parenthesis is encountered. Note that the open parenthesis only pops up and does not output.
(4) If any other operators are encountered, such as (” + “, “*”, “(“), etc., pop elements from the stack until a lower priority element is found (or the stack is empty). After these elements are popped, the encountered operators are pushed onto the stack. One thing to note is that we only pop “(” in the case of”) “, otherwise we don’t pop “(“).
(5) If you reach the end of the input, pop all the elements in the stack one by one.
Caculate() function design
(Node stack)
1) Iterate through the expression and put the encountered number on the stack first
2) Then read the operation operator such as “+”, pop the top element and the next element on the stack, perform the corresponding operation, and push the calculation result onto the stack.
3) Read the next element and place it directly on the stack.
4) Read the next element such as “”, pop the top element and the next element on the stack, perform 85, perform the corresponding operation, and push the calculation result onto the stack…… And so on. The last value is at the top of the stack.
For the decimal point processing algorithm
- How it works: First convert decimals into whole numbers, then divide by the corresponding weight of 10. If sum = sum * 10 + the value of the element, sum = sum * 10 + the value of the element,10 + j + 1, until the next element is not 0-9.
- The specific algorithm is as follows
I’m dealing with the minus sign
The negative sign occurs at the first element of the character array or after the opening parenthesis. To avoid confusion with the minus sign “-“, find the minus sign by determining whether the first element of the character array or the element after the left parenthesis is “-” and replace it with “M”. If the element is “M”, “-” is displayed. When calculating the suffix value, if the element is “M”, the following element values (including decimals) are converted to negative numbers.
Main program flow chart and each module call relation
Physical design
-
Based on the implementation of an array of contiguous storage space in memory, the C declaration defines a character stack frame structure, containing an array of characters, for infix to suffix expressions
-
The meaning of the corresponding node
-
Stack in and out operation
-
The C declaration defines an integer stack frame structure containing an array of integers used to evaluate postfix expressions.
-
The meaning of the corresponding node
-
Stack in and out operation
test
- The test case
- The test results
Source code (annotated)
The code is written in THE C language version, and the github code link of the Java version will be added later when there is time