c - C语言的RPN

Question

我对这段代码有疑问，它适用于较小的值，但较大的值会崩溃。

例如。

输入：

1+2+3

输出：

Expression:
1+2+3
Reverse Polish Notation:
12+3+ 
Result:
6

但是在这个例子中它崩溃了

input:
100+2*100/50
output:
runtime-error

此代码将中缀转换为后缀，并计算 RPN。

// C program to convert infix expression to postfix 
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h>
#include <string.h> 
#include <ctype.h>


struct Stack
{
    int top;
    unsigned capacity;
    int* array;
};

struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*)
        malloc(sizeof(struct Stack));

    if (!stack)
        return NULL;

    stack->top = -1;
    stack->capacity = capacity;

    stack->array = (int*)malloc(stack->capacity *
        sizeof(int));

    return stack;
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
char peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}
void push(struct Stack* stack, char op)
{
    stack->array[++stack->top] = op;
}

int isOperand(char ch)
{
    return (ch >= '0' && ch <= '9');
}

int Prec(char ch)
{
    switch (ch)
    {
    case '+':
    case '-':
        return 1;

    case '*':
    case '/':
        return 2;

    case '^':
        return 3;
    }
    return -1;
}

int infixToPostfix(char* exp)
{
    int i, k;

    struct Stack* stack = createStack(strlen(exp));
    if (!stack)
        return -1;

    for (i = 0, k = -1; exp[i]; ++i)
    {
        if (isOperand(exp[i]))
            exp[++k] = exp[i];
        else if (exp[i] == '(')
            push(stack, exp[i]);
        else if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                exp[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return -1;           
            else
                pop(stack);
        }
        else
        {
            while (!isEmpty(stack) &&
                Prec(exp[i]) <= Prec(peek(stack)))
                exp[++k] = pop(stack);
            push(stack, exp[i]);
        }

    }

    while (!isEmpty(stack))
        exp[++k] = pop(stack);

    exp[++k] = '\0';
    printf("Reverse Polish Notation:\n");

    char str[10];

    strcpy(str, exp);

    for (int i = 0; str[i]; i++)
    {
        printf("%c ", str[i]);
    }
    printf("\n");
}

int evaluatePostfix(char* exp)
{
    struct Stack* stack = createStack(strlen(exp));
    int i;

    if (!stack) return -1;

    for (i = 0; exp[i]; ++i)
    {
        if (isdigit(exp[i]))
            push(stack, exp[i] - '0');
        else
        {
            int val1 = pop(stack);
            int val2 = pop(stack);
            switch (exp[i])
            {
            case '+': push(stack, val2 + val1); break;
            case '-': push(stack, val2 - val1); break;
            case '*': push(stack, val2 * val1); break;
            case '/': push(stack, val2 / val1); break;
            }
        }
    }
    return pop(stack);
}


int main()
{
    //char exp[] = "1+2+3";
    char exp[10];
    scanf("%14s", exp);
    printf("Expression:\n%s\n", exp);

    infixToPostfix(exp);
    printf("Result:\n%d", evaluatePostfix(exp));
    return 0;
}

标签： cdata-structuresstack