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!