General idea of the topic
Link to Niuke topic
Give a string in the title to express an expression, and use the program to calculate the resulting value
AC code
#include<iostream> #include<stack> using namespace std; string origin_value; int position = 0; void input(){ cin >> origin_value; } int get_int(char c){ return c - '0'; } void deal_cmd(stack<int> &opreate_num,char cmd, int num){ switch(cmd){ case '+': opreate_num.push(num); break; case '-': opreate_num.push(-num); break; case '*': opreate_num.top() *= num; break; case '/': opreate_num.top() /= num; break; } } int calculate(stack<int> num){ int sum = 0; while(!num.empty()){ sum += num.top(); num.pop(); } return sum; } int deal_expression(){ int temp_num = 0 , value_len = origin_value.length(); char cmd = '+'; stack<int> opreate_num; // Set as a local variable (convenient for recursive calls) while(position < value_len){ // Here, while is used, and the global variable position is less than the length is directly used as the loop condition if(origin_value[position] == '('){ // '()' recursive call encountered // () execute first, but the operator execution order is consistent with that of the external position ++; temp_num = deal_expression(); } while(position < value_len && isdigit(origin_value[position])){ temp_num = temp_num * 10 + get_int(origin_value[position]); position ++; } deal_cmd(opreate_num, cmd, temp_num); temp_num = 0; cmd = origin_value[position]; if(origin_value[position] == ')'){ position ++; break; } position ++; } return calculate(opreate_num); } int main(){ input(); cout << deal_expression(); return 0; }
Code interpretation
input
Enter first. In order to facilitate the subsequent modification of the input format and inspection of the input, it is specially encapsulated as an input function
void input(){ cin >> origin_value; }
Processing expressions
After input, you need to process the expression
First, define variables in the function
- temp_num: the value of each calculation (temporarily required), which will be stored on the stack
- value_len: length of string, termination condition of loop
- cmd: four detected operations. The default is+
- opreate_num: specially set as a local variable to facilitate the storage of new operands when processing the () operator
After defining variables, execute the main logic
First, process () operation
The first thing to deal with is the operation of (), which directly recursively calls itself
Because the function finally returns the value of the current expression, and when it encounters (recursively calls itself, encounters) the end of the call, the return value
if(origin_value[position] == '('){ // '()' recursive call encountered // () execute first, but the operator execution order is consistent with that of the external position ++; temp_num = deal_expression(); } if(origin_value[position] == ')'){ position ++; break; }
Number of processes
Judge whether the position is legal, and if it is a number at present, perform the number operation
That is to calculate all the numbers before the symbols
while(position < value_len && isdigit(origin_value[position])){ temp_num = temp_num * 10 + get_int(origin_value[position]); position ++; }
Processing four arithmetic expressions
Judge the symbol corresponding to cmd
- +: save num directly
- -: the opposite number stored in num
- *: set stack top element * = current num
- /: set stack top element / = current num
void deal_cmd(stack<int> &opreate_num,char cmd, int num){ switch(cmd){ case '+': opreate_num.push(num); break; case '-': opreate_num.push(-num); break; case '*': opreate_num.top() *= num; break; case '/': opreate_num.top() /= num; break; } }
After processing, set temp_num is set to 0, and the operation symbol is updated
Return value
Since the operation is completed when the four operations are processed and stored in the stack
Therefore, when returning a value, you only need to add all the elements in the stack!
int calculate(stack<int> num){ int sum = 0; while(!num.empty()){ sum += num.top(); num.pop(); } return sum; }
Summary and analysis
When I saw this question, I felt it was very simple, but I didn't know how to start, and then I tried to use python to implement it
One line of code to solve
But after all, I still don't know how to implement it internally, so I went back to c++ implementation and began to understand stack and recursion
First of all, it's natural to think that you can call yourself recursively to record values when you encounter parentheses
Because the internal four operations of the brackets are also consistent with the external operations, only the internal operations are executed first to produce the results
And the value of each final operation needs to be added to the stack. The data can also be preprocessed when it is stored in the stack. For the subtraction operator, store the negative number directly, and the multiplication and division operations can directly modify the top element of the stack!