题解 | 四则运算

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX_STACK 1000

typedef struct
{
    int data[MAX_STACK];
    int top;
} Stack;

/* 初始化 */
int iniStack( Stack *s)
{
    return s->top=-1;
}

/* 判定空栈 */
int isEmpty( Stack *s)
{
    return s->top==-1;
}

/* 入栈 */
void push( Stack *s, int value )
{
    s->data[++(s->top)]=value;
}

/* 出栈 */
int pop ( Stack *s )
{
    return s->data[(s->top)--];
}

/* 获取栈顶元素 */
int peek( Stack *s)
{
    return s->data[s->top];
}

/* 运算符判定 */
int isoperator( char op)
{
    return op=='+'||op=='-'||op=='*'||op=='/';
}

/* 运算符优先级判定 */
int precedence( char op )
{
    if( op == '+'||op=='-') return 1;
    if( op == '*'||op=='/') return 2;
    return 0;
}
/* 负号判定 */
int isMuniSign( const char *expr, int pos)
{
    if( pos == 0 ) return 1;
    if( pos > 0 && (expr[pos-1]=='('||expr[pos-1]=='['||expr[pos-1]=='{')) return 1;
    if( pos > 0 && isoperator(expr[pos-1])) return 1;
    return 0;
}

/* 运算符计算 */
int calculate( int a, int b, char op)
{
    switch(op)
    {
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        case '/': return a/b;
    }

    return 0;
}

int calculateMain( char *expr )
{
    Stack numStack;
    Stack opStack;

    iniStack(&numStack);
    iniStack(&opStack);

    int i= 0;
    int len = strlen(expr);

    while(i < len)
    {
        /* 遇到空格不处理 */
        if( expr[i] == ' ')
        {
            i++;
            continue;
        }

        /* 数字入栈 */
        if( isdigit(expr[i]) )
        {
            int num=0;
            while( i<len && isdigit(expr[i]) )
            {
                num=num*10+(expr[i]-'0');
                i++;
            }
            push(&numStack, num );
            continue;
        }

        /* 左括号入栈 */
        if( expr[i] == '(' || expr[i] == '[' || expr[i] == '{' )
        {
            push(&opStack, expr[i]);
            i++;
            continue;
        }
        
        /* 负号处理   0-X=-X */
        if(expr[i] == '-' && isMuniSign(expr, i) )
        {
            push(&numStack, 0);
            push(&opStack, '-');
            i++;
            continue;
        }

        /* 运算符 */
        if( isoperator(expr[i]) )
        {
            while( !isEmpty(&opStack) && precedence(peek(&opStack)) >= precedence(expr[i]))
            {
                char curop = pop(&opStack);
                int b = pop(&numStack);
                int a = pop(&numStack);
                int res = calculate(a, b, curop);
                push(&numStack, res );
            }

            push(&opStack, expr[i]);
            i++;
            continue;
        }

        /* 右括号 */
        if( expr[i] == ')' || expr[i] == ']' || expr[i] == '}' )
        {
            while( !isEmpty(&opStack) && 
				  ((expr[i] == ')' && peek(&opStack) != '(') || 
				   (expr[i] == ']' && peek(&opStack) != '[') || 
				   (expr[i] == '}' && peek(&opStack) != '{') ) )
            {
                char curop = pop(&opStack);
                int b = pop(&numStack);
                int a = pop(&numStack);
                int res = calculate(a, b, curop);
                push(&numStack, res );
            }
            /* 符号栈对应左括号出栈 */
            pop(&opStack);
            i++;
            continue;
        }
    }

    while( !isEmpty(&opStack) ) 
    {
        char curop = pop(&opStack);
        int b = pop(&numStack);
        int a = pop(&numStack);
        int res = calculate(a, b, curop);
        push(&numStack, res );
    }

    return peek(&numStack);
}

int main() 
{
    char expr[MAX_STACK];

    scanf("%s", expr);

    int iresult = calculateMain(expr);
    printf("%d\n", iresult);
    return 0;
}