In the last article we talked about how to convert an infix expression into a postfix expression, and we also gave a simple example of how to calculate an infix expression (see # data structure topic note -03- Infix expression into a postfix expression C).

Here we’ll take a slightly more complicated example and attach the steps

Example suppose we want to compute a formula: ‘9 3 1-3 x + 10 2 / +’

Elements scanned Digital stack S(bottom of heap -> top of heap) explain
9 9 Push the
3 September 3 Push the
1 9 3 1 Push the
– September 2 When the operator ‘-‘ is encountered, press 1 3 to implement operation 3-1 =2 and press on stack S
3 2, 3, 9 Push the
x September 6 When operator ‘x’ is encountered, press out 3 2 to implement operation 3 x 2 =6 and press onto stack S
+ 15 When the operator ‘+’ is encountered, press out 6. 9 implements the operation 6 + 9=15 and pushes onto the stack S
10 15 October Push the
2 15 October 2 Push the
/ 15 May When the operator ‘/’ is encountered, press out 2 10 to implement operation 10/2 =5 and press onto stack S
+ 20 When the operator ‘+’ is encountered, press out 5. 15 implements operation 15 + 5=20 and pushes onto stack S
The scan 20 The results of

Code implementation

Define a stack

typedef struct SNode *Stack;
typedef int Position;
typedef int ElementType;
#define MAXSIZE 30

struct SNode{
    ElementType Data[MAXSIZE];
    Position Top;
};
Copy the code

Initialize a stack

Stack Create(){
    Stack S;
    S=(Stack)malloc(sizeof (struct SNode));
    S->Top=-1;
    return S;
}
Copy the code

Onto the stack

void Push(ElementType X,Stack S){
    if(IsFull(S)){
        printf("The stack is full! \n");
        return;
    } else{ S->Top++; S->Data[S->Top]=X; }}Copy the code

Press out the top element

ElementType Pop(Stack S){
    ElementType X;
    if(IsEmpty(S)){
        printf("Stack empty! \n");
        return -1;
    } else{
        X=S->Data[S->Top];
        S->Top--;
        returnX; }}Copy the code

Function to evaluate postfix expressions

int suffixExpressionCalculation(char* str){
    int i=0;
    Stack S;
    S=Create();
    ElementType number_to_push,num1,num2;
    while(str[i] ! ='\ 0') {if(str[i] ! =' ') {// Skip the space
            if(str[i] >= '0' && str[i]<='9') {/ / is digital
                number_to_push=0;
                while(str[i] ! =' ' && str[i]){
                    number_to_push=10*number_to_push+(str[i]-'0');
                    i++;// Make sure that connected numbers such as 123 are converted to 123 without breaking apart
                }
                Push(number_to_push,S);
            } else{
                num2=Pop(S);
                num1=Pop(S);
                switch (str[i]) {
                    case '+':{
                        num1+=num2;
                        break;
                    }
                    case The '-':{
                        num1-=num2;
                        break;
                    }
                    case The '*':{
                        num1*=num2;
                        break;
                    }
                    case '/':{
                        num1/=num2;
                        break;
                    }
                }
                Push(num1,S);
            }
        }
        i++;
    }
    num1=Pop(S);
    return num1;
}
Copy the code

Auxiliary function

int IsFull(Stack S){
    if(S->Top == MAXSIZE-1) {return 1;
    }
    return 0;
}

int IsEmpty(Stack S){
    if(S->Top == -1) {return 1;
    }
    return 0;
}
Copy the code