题解 | #四则运算#

#include<stdio.h>

int isOPND(int x);//判断x是否为运算数据

typedef struct stack{
    int *base;
    int *top;
}stack;
stack s;

void push(int x);
int pop();

int compare(char x, int *y);//比较符号优先级，1为x比栈顶优先

int cal(int output[]);//计算后缀表达式的结果

int function(int i);//根据不同运算符'+', '-', '*', '/'，转化为优先级，无关紧要的函数

//因为char数据范围不够，所以用int进行存储和计算。为区分运算符和运算数据，运算符以char的值存储，运算数据以 本身数值+'0' 的值存储
int main(){
    char x;
    int output[1000]={0};
    s.base=(int *)malloc(1000*sizeof(int));
    s.top=s.base;
    int i=0;
    int flag=0;//用来处理大于9的两位数输入
    int flag1=0;//用来处理莫名其妙的负数
    while(scanf("%c", &x)!=EOF){
        if(x=='\n')    break;
        if(isOPND((int)x)){
            if(flag==0){
                output[i++]=x;
                flag=1;
                flag1=1;
            }
            else{
                output[i-1]=(output[i-1]-'0')*10+x;
                flag1=1;
            }
        }
        else if(x=='-'&&flag1==0){//用来处理负数
            scanf("%c", &x);
            x=(-1)*(x-'0')+'0';
            output[i++]=x;
            flag=1;
        }
        else if(x=='('||x=='['||x=='{'){
            push((int)x);
            flag=0;
        }
        else if(x==')'||x==']'||x=='}'){
            while(*(s.top-1)!='('&&*(s.top-1)!='['&&*(s.top-1)!='{'){
                output[i++]=pop();
            }
            pop();
            flag=0;
        }
        else{
            if(compare(x, s.top-1)==1){//优先级高于栈顶
                push((int)x);
            }
            else{
                while(s.top!=s.base&&compare(x, s.top-1)!=1){
                    output[i++]=pop();
                }
                push(x);
            }
            flag=0;
        }
    }
    while(s.top!=s.base){//输出剩余的运算符
        output[i++]=pop();
    }
    printf("%d\n", cal(output));
    return 0;
}


void push(int x){
    *(s.top++)=x;
}

int pop(){
    return *(--s.top);
}

int isOPND(int x){//因为存在大于9的多位数数据，所以不能简单用字符'0'-'9'的范围来判断，故出此下策
    if(x!='+'&&x!='-'&&x!='*'&&x!='/'&&x!='('&&x!='['&&x!='{'&&x!=')'&&x!=']'&&x!='}')
        return 1;
    return 0;
}

int compare(char x, int *y){
    int x1, y1;
    x1=function((int)x);
    y1=function(*y);
    if(x1>y1)    return 1;
    else if(x1==y1)    return 0;
    else    return -1;
}

int function(int i){
    switch(i){
        case '+':
            return 1;
        case '-':
            return 1;
        case '*':
            return 2;
        case '/':
            return 2;
    }
    return 0;
}

int cal(int output[]){
    int x=0;
    int i=0;
    for( ; isOPND(output[i])==1; i++){
        push(output[i]);
    }
    for( ; output[i]!=0; i++){
        if(isOPND(output[i])==1){
            push(output[i]);
        }
        else{
            switch(output[i]){
            case '+':
                x=(*(s.top-2)-'0')+(*(s.top-1)-'0');
                pop();
                pop();
                push(x+'0');
                break;
            case '-':
                x=(*(s.top-2)-'0')-(*(s.top-1)-'0');
                pop();
                pop();
                push(x+'0');
                break;
            case '*':
                x=(*(s.top-2)-'0')*(*(s.top-1)-'0');
                pop();
                pop();
                push(x+'0');
                break;
            case '/':
                x=(*(s.top-2)-'0')/(*(s.top-1)-'0');
                pop();
                pop();
                push(x+'0');
                break;
            }
        }
    }
    return x;
}