【C语言】表达式求值问题，应用“栈”编写一个计算器

Question

【C语言】表达式求值问题，应用“栈”编写一个计算器，要求:
a)支持整数（长整型范围内）四则混合运算；
b)输入应是中缀表达式，对不合法的输入应有提示；
c)能够输出正确计算结果;
d)示例如输入5*(10-3)/7 ,输出结果5

Answer 1

我有现成程序，你试试：

 #include<ctype.h>  
#include<stdlib.h>  
#define stacksize 30  
#define stackincrease 30  
#define maxvalume 30  
#define expvalume 200  
#define title "------------------------------Life is a fight!------------------------------------"  

typedef float Elemtype;

typedef struct STACK{
    Elemtype* top;
    Elemtype* base;
    int len;
} stack;

stack* InitStack()
{
    Elemtype* t;
    stack* s;
    t = (Elemtype*)malloc(stacksize*sizeof(Elemtype));
    s = (stack*)malloc(sizeof(stack));
    s->top = t;
    s->base = t;
    s->len = stacksize;
    return s;
}

void PushStack(stack *s, Elemtype d)
{
    if (s->top - s->base >= s->len - 1)
        s->base = (Elemtype*)realloc(s->base, (s->len + stackincrease)*sizeof(Elemtype));
    *s->top = d;
    s->top++;
}

void PopStack(stack* s, Elemtype* d)
{
    if (s->top == s->base)
    {
        printf("\nErr!\n");
        return;
    }
    *d = *--(s->top);
}

int LengthStack(stack *s)
{
    return (s->top - s->base);
}

int GetExp(Elemtype* str)
{
    char c;
    int i = 0;
    fflush(stdin);
    scanf("%c", &c);
    while (c != '\n')
    {
        if (i > expvalume)
        {
            printf("Err: The expression is too long!\n");
            return -1;
        }
        *str++ = c;
        i++;
        scanf("%c", &c);
    }
    if (i == 0)
    {
        *str++ = '#';
    }
    *str = '\0';
    return i;
}

void NiftoSuf(Elemtype* nif, Elemtype* suf)
{
    int i, j, n;
    Elemtype c, t;
    stack *s;

    i = 0;
    j = 0;
    s = InitStack();
    c = nif[i];
    while (c != '#')
    {
        while (isdigit(c) || c == '.')
        {
            suf[j++] = c;
            c = (char)nif[++i];
            if ((c<'0' || c>'9') && c != '.')
            {
                suf[j++] = ' ';
            }
            suf[j] = '\0';
        }
        if (c == ')')
        {
            PopStack(s, &t);
            while (t != '(')
            {
                suf[j++] = t;
                suf[j++] = ' ';
                PopStack(s, &t);
            }
            suf[j] = '\0';
        }
        else if (c == '(')
            PushStack(s, c);
        else if (c == '+' || c == '-')
        {
            if (!LengthStack(s))
            {
                PushStack(s, c);
            }
            else
            {
                do{
                    PopStack(s, &t);
                    if (t == '(')
                    {
                        PushStack(s, t);
                    }
                    else
                    {
                        suf[j++] = t;
                        suf[j++] = ' ';
                        suf[j] = '\0';
                    }
                } while (LengthStack(s) && t != '('&&c != '(');
                PushStack(s, c);
            }
        }
        else if (c == '*' || c == '/' || c == '(')
        {
            PushStack(s, c);
        }
        else if (c == '#')
        {
            while (LengthStack(s))
            {
                PopStack(s, &t);
                suf[j++] = t;
                suf[j++] = ' ';
            }
            break;
        }
        else
        {
            printf("\nErr:Expression Error\n");
            return;
        }
        i++;
        c = nif[i];
    }
    if (c == '#')
    while (LengthStack(s))
    {
        PopStack(s, &t);
        suf[j++] = t;
        suf[j++] = ' ';
    }
    suf[j++] = '#';
    suf[j] = '\0';
    free(s);
}

Elemtype Cal(Elemtype* suf)
{
    int i, j;
    char c;
    Elemtype f, r, d1, d2;
    stack *s;

    i = 0;
    j = 0;
    s = InitStack();
    char t[maxvalume];
    c = suf[j++];
    while (c != '#')
    {
        while (isdigit(c) || c == '.')
        {
            if (i > maxvalume)
            {
                printf("Err: The data is too large!\n");
                return -1;
            }
            t[i++] = c;
            t[i] = '\0';
            c = suf[j++];
            if (c == ' ')
            {
                f = atof(t);
                PushStack(s, f);
                i = 0;
            }
        }
        switch (c){
        case '+':
            PopStack(s, &d2);
            PopStack(s, &d1);
            PushStack(s, d1 + d2);
            break;
        case '-':
            PopStack(s, &d2);
            PopStack(s, &d1);
            PushStack(s, d1 - d2);
            break;
        case '*':
            PopStack(s, &d2);
            PopStack(s, &d1);
            PushStack(s, d1*d2);
            break;
        case '/':
            PopStack(s, &d2);
            if (d2 == 0)
            {
                printf("Err: data error!\n");
                return  -1;
            }
            PopStack(s, &d1);
            PushStack(s, d1 / d2);
            break;
        }
        c = suf[j++];
    }
    PopStack(s, &r);
    printf("Result: %f", r);
    free(s);
    return r;
}

int main(void)
{
    int i, j, k;
    char c, c1, y;
    Elemtype nif[expvalume], suf[expvalume];
    printf("%s\n\n", title);

    do{
        i = 0;
        j = 0;
        k = 0;
        printf("Please enter the expression:\n");
        GetExp(nif);
        NiftoSuf(nif, suf);
        printf("\n");
        while (suf[k] != '\0')
        {
            c1 = suf[k];
            printf("%c", c1);
            k++;
        }
        printf("\n\n");
        Cal(suf);
        printf("\n\n\n");
        printf("\nPlease enter 'Y' for continual\n");
        scanf("%c", &y);
        printf("\n");
        fflush(stdin);
    } while (y == 'Y' || y == 'y');
    return 0;
}