Abstract: I have been in the lab for two weeks. In the words of my elder brother, I am basically in a high state. Teacher zhang asked how C++ learning? Can you make up a simple calculator? I didn’t think this calculator could be as simple as just adding, subtracting, multiplying, and dividing, so I thought about writing a calculator that could handle parentheses, preferably a simple UI. In the process of thinking, it is found that the difficulty of this calculator is how to convert infix expression into postfix expression and how to calculate postfix expression.
method
The thinking of people
This is the fastest and most accurate method if it’s just for solving problems. But it doesn’t work with computers. The following uses a+b*c+(d*e+f)*g as an example to show how to convert an infix expression to a suffix.
-
Parentheses are added and subtracted, then multiplied and divided
Results: ((a + b * c)) + (+ f (e) (d *) * g))
-
Replace each expression in parentheses with a suffix from the inside out
Final result: ABC *+de*f+g*+
This gives the final result of the infix expression to the suffix expression. This method is effective in dealing with examinations.
Computer Thinking
After all, computers are not like people. They are “stupid”. It doesn’t work with the human mind. So how does it convert an infix expression into a postfix expression?
Computer ideas need to use stack, first to clarify the rules of infix expression to suffix expression:
1) If we encounter an operand, we 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 we get to the end of the input, pop all the elements in the stack one by one.
A +b*c+(d*e+f)*g The following description of the stack is directly described in text, from left to right from the bottom of the stack to the top of the stack. Null indicates that the stack is empty
-
Traversing the expression from left to right, first encountering a, prints it directly.
The output is: a
The stack case is empty
-
We keep iterating, we hit +, we put it on the stack.
The output is: a
Stack case: +
-
So we’re going to iterate, we’re going to print b.
The output is ab
Stack case: +
-
As we continue through, we encounter *, which has a higher priority than + at the top of the stack, so we put * on the stack.
The output is ab
Stack case: +*
-
Keep iterating, and when you see c, print it out.
The output is: ABC
Stack case: +*
-
Continue traversing, encounters +, because + has a lower priority than * at the top of the stack, will pop *; Then the + of the new top element has the same priority as the +, so it also pops the + of the current top element. And then when the stack is empty, I put this + on the stack.
The output is ABC *+
Stack case: +
-
Continue traversing, encountered (, put it directly on the stack, not encountered) will not pop (.
The output is ABC *+
Stack case: +(
-
So I’m going to go through, and I’m going to print d.
The output is: ABC *+d
Stack case: +(
-
Continue traversing, encountered *, because the top of the stack is (, not encountered) does not pop (, so directly put * on the stack.
The output is: ABC *+d
Stack case: +(*
-
Continue iterating, and when you see e, just print it out.
The output is ABC *+de
Stack case: +(*
-
Continue traversing, encountered +, because + has lower priority than the top of the stack *, * is popped; The new top element of the stack is (, not encountered) does not pop (, so + is put on the stack.
The output is ABC *+de*
Stack case: +(+
-
Continue iterating. If you see f, print it out.
The output is ABC *+de*f
Stack case: +(+
-
Continue traversing, encountered), directly pop stack elements and output until encountered (note :(pop but not output.
The output is ABC *+de*f+
Stack case: +
-
As we continue through, we encounter *, which has a higher priority than the top element +, so we push * directly onto the stack.
The output is ABC *+de*f+
Stack case: +*
-
Continue iterating, and when you see g, print it out.
The output is ABC *+de*f+g
Stack case: +*
-
Continue traversal, null, traversal ends. Pop the stack elements one by one.
The output is ABC *+de*f+g*+
The stack case is empty
At this point, the infix expression suffixes are complete, resulting in ABC *+de*f+g*+.
Code implementation
The source code
The code is written in C++, but with a process-oriented approach. The code is as follows:
// Infix expression suffixes
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int prio(char op) { // Sort the operator by priority
int priority;
if (op == The '*' || op == '/')
priority = 2;
if (op == '+' || op == The '-')
priority = 1;
if (op == '(')
priority = 0;
return priority;
}
bool Trans(string &str,string &str1) { // Reference passing
stack<char> s; // define a stack s of type char
int i;
for (i = 0; i<str.size(); i++) {
if (str[i] >= '0' && str[i] <= '9') { // If it is a number, push it directly
str1+=str[i];
}
else { // Otherwise not a number
if (s.empty()) // if the stack is empty, it will enter
s.push(str[i]);
else if (str[i] == '(') // open parenthesis on the stack
s.push(str[i]);
else if (str[i] == ') ') { // If it is a close parenthesis, as long as the top of the stack is not an open parenthesis, it pops and prints
while(s.top() ! ='(') {
str1+= s.top();
s.pop();
}
s.pop(); // Open parenthesis, but no output
}
else {
while (prio(str[i]) <= prio(s.top())) { // The top priority of the stack is greater than or equal to the current operator
str1+= s.top();
s.pop();
if (s.empty()) // Stop if the stack is empty
break;
}
s.push(str[i]); // push the current operator onto the stack}}}while(! s.empty()) {// Finally, if the stack is not empty, all elements are popped and output
str1+= s.top();
s.pop();
}
return true;
}
int main(a) { / / main program
string infix;
string postfix;
cout << "Please enter infix expression:" << infix << endl;
cin >> infix;
Trans(infix,postfix);
cout << "Postfix expression is:" << postfix << endl;
return 1;
}
Copy the codeProgram testing
Here we use a+b*c+(d*e+f)*g instance 1+2*3+(4*5+6)*7 to test our program, it can be seen that the running result is 123*+45*6+7*+, calculation is correct.
conclusion
When writing this little program, there are some small gains. After all, is a beginner, the mistakes made are very low-level intellectual mistakes, understanding is not in place, the foundation is not solid. I would like to thank my undergraduate classmate Bai Yang for her patience in teaching me.
1) Do not use the subscript of the string class object when the size is not initialized, it will appear string subscript out of range error. Occurs on the third iteration of the loop, presumably because the default size of the string object is 2 bytes.
2) String objects do not end in ‘\0’, to distinguish from C language, use size() to judge its end. The size() function returns the size, and the subscripts start at 0, so up to size-1.
3) Function calls should be passed by reference when they are conformal.
4) #include<stack>