c - 使用链表的 RPN 计算器

Question

我的代码遇到问题。它似乎只适用于单位数字 int。我不知道如何创建一个适用于大于 9 的 int 的函数。此外，我不知道如果字符串为空，如何结束程序。

这是我的代码:

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

//stack type
struct node
{
    int head;
    int *array;
    unsigned capacity;
};

struct node* createNode();
int isEmpty();
char pop();
void push(struct node* stack, char op);
int evaluatePostfix();

int main()    {
    char exp[1000]; // = "5 1 2 + 4 * + 3 -";
    printf("Input string:\t");
    fgets(exp, 1000, stdin);
    for(int i = 1 ; i <= strlen(exp); i++) {
        if(exp[i] == '\n') {
            exp[i] = '\0';
        }
        else if (exp[0] == '\n') {
            printf("stack is empty\n");
            exit(0);
        }
    }
    printf ("%s = %d\n", exp, evaluatePostfix(exp));
    return 0;
}

struct node* createNode(unsigned capacity)  {
    struct node* stack = (struct node*) malloc(sizeof(struct node));

    if (!stack) return NULL;

    (*stack).head = -1;
    (*stack).capacity = capacity;
    (*stack).array = (int*) malloc((*stack).capacity *sizeof(int));

    if (!(*stack).array) return NULL;

    return stack;
}

int isEmpty(struct node *stack) {
    return (*stack).head == -1 ;
}


char pop(struct node* stack)    {
    if (!isEmpty(stack))
    return (*stack).array[(*stack).head--] ;
    return '$';
}


void push(struct node* stack, char op)  {
    (*stack).array[++(*stack).head] = op;
}

// The main function that returns value of a given postfix expression 
int evaluatePostfix(char* exp)  {

// Create a stack of capacity equal to expression size
    struct Stack* stack = createStack(strlen(exp));
    struct node *stack = createNode(strlen(exp));
    if (!stack) return -1;

// Scan all characters one by one

for (int i = 0; exp[i]; ++i){
    // If the scanned character is an operand or number,
    // push it to the stack.    
   if ((exp[i])== ' ') continue;
   else if (isdigit(exp[i]))
        push(stack, exp[i] - '0');


    //  If the scanned character is an operator, pop two
    // elements from stack apply the operator 
    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);
}

Answer 1

我无法为您写出全部内容，但可以为您指明正确的方向。首先，当有人说“库函数 XYZ() 对你有帮助”时，你应该去阅读手册页中有关该函数的信息。例如，从 Linux shell 运行:man atoi 以了解 atoi 函数。

对于您的特定问题，它可以归结为解析字符串并将其转换为数字和运算符。因此，一些有用的库函数是:

• strtok:从较长的字符串中提取分隔的字符串标记。您可以使用它来获取每个单独的输入。
• atoi:这可以将数字的字符串表示形式转换为其等效的整数。不允许进行错误检查。
• strtol:可以执行与 atoi 相同的操作(以及更多)，并且还允许进行错误检查。

考虑到这些信息，下面是一个可能对您有用的代码片段:

int evaluatePostfix(char* exp)
{
    char *token;
    long int number;

    /* strtok will keep extracting the next token delimited by space */
    while (token = strtok(exp, " ")) {

        /* Now parse the token and process it */
        if (is_operator(token)) {
            /* do operator processing */
        } else {
            number = strtol(token, NULL, 10);
            /* do number processing */
        }
    }

    /* strtok returns NULL when no more tokens. So
       we are done when the while loop exits */
}

请注意，上面的代码不会对 strtol 进行错误检查。您可能想这样做。阅读 strtol 的手册页以了解如何对其进行错误检查。