题解 | 牛牛与后缀表达式

//C语言自己写栈再加上一些对字符串的处理
#include <stdlib.h>
#define MaxSize 1000000

struct SqStack{
    int top;
    long long data[MaxSize];
};

void InitStack(struct SqStack *S){
    S->top = -1;
}

int EmptyStack(struct SqStack S){
    if(S.top == -1){
        return 1;
    }
    else{
        return 0;
    }
}

int Push(struct SqStack *S, long long c){
    if(S->top == MaxSize - 1){
        return 0;
    }
    else{
        S->data[++S->top] = c;
        return 1;
    }
}

int Pop(struct SqStack *S, long long *c){
    if(S->top == -1){
        return 0;
    }
    else{
        *c = S->data[S->top--];
        return 1;
    }
}

int Top(struct SqStack S, long long *x){
    if(S.top == -1){
        return 0;
    }
    else{
        *x = S.data[S.top];
        return 1;
    }
}


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定一个后缀表达式，返回它的结果
 * @param str string字符串 
 * @return long长整型
 */
long long legalExp(char* str ) {
    // write code here
    struct SqStack S;
    InitStack(&S);
    char num[20] = "";
    for(int i = 0; i < MaxSize && str[i] != '\0'; i ++){
        if(str[i] == '+' ){
            long long x, y;
            int r1 = Pop(&S, &y);
            int r2 = Pop(&S, &x);
            if(r1 && r2){
                long long z = x + y;
                Push(&S, z);
            }
        }
        else if(str[i] == '-' && S.top >= 1 ){
            long long x, y;
            int r1 = Pop(&S, &y);
            int r2 = Pop(&S, &x);
            if(r1 && r2){
                long long z = x - y;
                Push(&S, z);
            }
        }
        else if(str[i] == '*' ){
            long long x, y;
            int r1 = Pop(&S, &y);
            int r2 = Pop(&S, &x);
            if(r1 && r2){
                long long z = x * y;
                Push(&S, z);
            }
        }
        else{
            if(str[i] != '#'){
                strncat(num,str + i,1);
            }
            else{
                long long x = strtoll(num, NULL, 10);
                Push(&S,x);
                memset(num, 0, sizeof(num));
            }
           
        }
    }
    long long result;
    int r = Top(S,&result);
    return result;
}