C-K&R 表达式 : evaluate a reverse Polish expression from the command line

Question

我一直在尝试使用动态分配的堆栈来完成 K&R 的练习 5-10。我的代码基于第 4 章的代码(他们使用全局变量来实现堆栈)。问题是我的程序根本不起作用，我不知道出了什么问题。代码如下:

/* expr: evaluates a reverse Polish expression from the command line */

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

#define MAXOP 100 /* maximal operator length */
#define NUMBER '0' /* signal that a number was found */

int getop(char *argv);
void push(double **top, double val);
double pop(double **top);

int main(int argc, char *argv[])
{
     if (argc == 1) {
        printf("usage: evaluate a reverse Polish expression from the command line\n");
    return 1;
}

double *stack = malloc((argc-1)*sizeof(double));

if (stack == NULL) {
    printf("error: couldn't allocate enough space for the stack\n");
    return 2;
}

int i, type;
double op1, op2, *top = stack; /* top points to the next free stack position */
char s[MAXOP];

for (i = 1; argv[i] != NULL; i++) {
    type = getop(argv[i]);
    switch (type) {
        case NUMBER :
            push(&top, atof(argv[i]));
            break;
        case '+' :
            op2 = pop(&top);
            op1 = pop(&top);
            push(&top, op1+op2);
            break;
        case '-' :
            break;
        case '*' :
            break;
        case '/' :
            break;
        case '%' :
            break;
        default :
            printf("error: unknown command %s\n", argv[i]);
            return 3;
            break;
    }
}
printf(" = %.8g\n", pop(&top));
free(stack);
return 0;
}

 int getop(char *argv)
{
int i, c;

if (!isdigit(argv[0]))
    return argv[0];
else
    return NUMBER;
}

void push(double **top, double val)
 {
    **top = val;
    (*top)++;
/* is error checking needed? */
}

double pop(double **top)
{
   (*top)--;
    return *(*top+1);
/* is error checking needed? */
}

似乎没有考虑运算符 - 例如输入 ./expr 1 12 13++ 产生输出 13。

编辑:感谢所有帮助人员，事实证明，push 和 pop 无法正常工作。我已经设法修复了该代码，尽管现在事后看来，我可以在编写代码之前做好更好的准备。

以下是更改后的代码:

/* expr: evaluates a reverse Polish expression from the command line */

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

#define MAXOP 100 /* maximal operator length */
#define NUMBER '0' /* signal that a number was found */

int getop(char *argv);
void push(double **top, double val);
double pop(double **top);

int main(int argc, char *argv[])
{
     if (argc == 1) {
        printf("usage: evaluate a reverse Polish expression from the command line\n");
    return 1;
}

double *stack = (double*) malloc((argc-1)*sizeof(double));

if (stack == NULL) {
    printf("error: couldn't allocate enough space for the stack\n");
    return 2;
}

int i, type;
double op1, op2, *top = stack; /* top points to the next free stack position */
char s[MAXOP];

for (i = 1; argv[i] != NULL; i++) {
    type = getop(argv[i]);
    switch (type) {
        case NUMBER :
            push(&top, atof(argv[i]));
            break;
        case '+' :
            op2 = pop(&top);
            op1 = pop(&top);
            push(&top, op1+op2);
            break;
        case '-' :
            op2 = pop(&top);
            op1 = pop(&top);
            push(&top, op1-op2);
            break;
        case 'x' :
            op2 = pop(&top);
            op1 = pop(&top);
            push(&top, op1*op2);
            break;
        case '/' :
        op2 = pop(&top);
            op1 = pop(&top);
        if (op2 != 0)
                push(&top, op1/op2);
        else {
        printf("error: division by zero\n");
                return 3;
        }
            break;
        default :
            printf("error: unknown command %s\n", argv[i]);
            return 4;
            break;
    }
}
printf(" = %.8g\n", pop(&top));
free(stack);
return 0;
}

 int getop(char *argv)
{
int i, c;

if (!isdigit(argv[0]))
    return argv[0];
else
    return NUMBER;
}

void push(double **top, double val)
 {
    **top = val;
    (*top)++;
}

double pop(double **top)
{
    double temp = *(*(top)-1);
    (*top)--;
    return temp;
}   

Answer 1

您的代码似乎不明白您使用malloc分配了一个数组，并且您正在尝试使用与基于指针的堆栈一起使用的“添加到前面”方法。您应该在将最近的项目插入堆栈后插入新值，并弹出最近插入堆栈的项目(即在堆栈的“末尾”)。

以下内容应该适合您。请注意，pcount是指向堆栈上项目数的指针，否则您将不知道堆栈是否为空(例如2 +将是无效输入，因为+ 需要 2 个值，但堆栈上只有 1 个值)，甚至在哪里添加另一个值，因为您无法确定堆栈的“结束”位置。

#include <math.h>    // for HUGE_VAL; may need to link the math library?

// Push a value onto the stack and update the number of items on the stack.
void push(double *stk, double value, int *pcount)
{
    // Add new values at the end of the stack (technically after the last item pushed).
    stk[*pcount] = value;
    ++*pcount;
}

// Pop a value off the stack and update the number of items remaining on the
// stack. If there are no values, HUGE_VAL is returned. Since it is possibly
// a valid value on some implementations, checking for an error should be done
// using the value pcount points to:
//
//     n = pop(stk, &stkCount);
//     if (stkCount < 0) {
//         // error: stack had no elements before pop
//     }
//
double pop(double *stk, int *pcount)
{
    if (*pcount >= 0) {
        // Remove items from the end of the stack.
        --*pcount;
        return stk[*pcount];
    }
    return HUGE_VAL;
}