c - 为什么我的 Infix to postfix 程序给出了错误的输出(C，Stacks)

Question

简介:我正在使用静态字符堆栈(使用结构和字符数组)在 C 编程语言中编写后缀程序的中缀。

我的方法论:我通常从工作代码开始，然后(当我知道算法有效时)使代码更清晰、更小。

完成:我只完成了我的程序的基本粗略代码，它给我错误的输出，所以我自己检查了几次并向我的 friend 展示了它，他也不能'不太明白。

问:如果有人可以看一下并告诉我为什么我得到错误的输出，如果可能的话，请指出我，这真的会帮助我，并可能使我成为更好的程序员正确的方向。

Insight: 我遇到的问题是，它不是在字母数字部分后添加 +、-、* 或/(就像 A+B 将是 AB+)，而是给出随机字符他们的位置(像 AB| 或 AB├ 等)。这些字符在每次执行程序时都会发生变化。我相信它们是垃圾值，但不确定它们是如何被使用的。

代码:

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

#define MAX 20

struct stackObj{

    char stack[MAX];
    int topOfStack;

};

void stackPush(struct stackObj *s, char value);
char stackPop(struct stackObj *s);
void stackPeekPrint(struct stackObj *s);
char stackPeek(struct stackObj *s);
int stackIsEmpty(struct stackObj *s);
int stackIsFull(struct stackObj *s);

int comparePrecedence(struct stackObj *s, char value);


int main(){

    struct stackObj s;
    s.topOfStack=0;

    char result[MAX];
    int resultFlag=0;

    char exp[MAX];
    gets(exp);

    printf("\n\n");
    printf("Expression:\t");
    printf(exp);
    printf("\n\n");


    char _new='.';
    char _old='.';
    int i=0;
    while (exp[i]!= '\0'){

        _new = exp[i];
        i++;

        if (_new=='+' || _new=='-' || _new=='*' || _new=='/'){

            if (comparePrecedence(&s,_new)==1){
                stackPush(&s,_new);

            } else if (comparePrecedence(&s,_new)==0){
                _old = stackPop(&s);
                result[resultFlag]=_old;
                resultFlag++;
                stackPush(&s,_new);
            }

        } else  if (_new=='('){
            stackPush(&s,_new);
        }

        else  if (_new==')'){
            _old = stackPop(&s);
            while (_old != '('){
                result[resultFlag]=_old;
                resultFlag++;
                _old = stackPop(&s);
            }
            stackPop(&s);

        } else if (isalnum(_new) ) {
            result[resultFlag]=_new;
            resultFlag++;
        }
    }

    while (s.topOfStack > 0) {
        _old = stackPop(&s);
        result[resultFlag]=_old;
        resultFlag++;

    }

    printf("\n\n\n");
    printf(result);
    printf("\n\n\n");


    return 0;
}

//----------------- Precedence Comparison CODE -----------------------------

int comparePrecedence(struct stackObj *s, char value){

    //START - Variable Declarations and Definitions
    int stackPrecedence = 0;
    int operatorPrecedence = 0;

    char stackChar = stackPeek(s);
    char operChar = value;
    //END - Variable Declarations and Definitions


    //START - Setting Precedences
    if (stackChar== '+'){ stackPrecedence=1; }
    else if (stackChar== '-'){ stackPrecedence=1; }
    else if (stackChar== '*'){ stackPrecedence=2; }
    else if (stackChar== '/'){ stackPrecedence=2; }

    if (operChar== '+'){ operatorPrecedence=1; }
    else if (operChar== '-'){ operatorPrecedence=1; }
    else if (operChar== '*'){ operatorPrecedence=2; }
    else if (operChar== '/'){ operatorPrecedence=2; }
    //END - Setting Precedences


    //START - Comparing Precedences
    if (operatorPrecedence > stackPrecedence) { return 1;
    } else { return 0; }

}


//----------------- STACK CODE ------------------------------------------

void stackPush(struct stackObj *s, char value){

    if ( (stackIsFull(s) != 1) && (s->topOfStack != MAX) ){

        s->stack[s->topOfStack] = value;
        s->topOfStack++;

    } else {
        printf("\nSorry, stack is full. No new data can be entered");
    }


}

char stackPop(struct stackObj *s){

    s->topOfStack = s->topOfStack-1;
    return s->stack[s->topOfStack-1];


}

void stackPeekPrint(struct stackObj *s){

    if (s->topOfStack != 0){
        printf("\nTOS:\t%c", s->stack[(s->topOfStack)-1]);
    } else {
        printf("\nSorry stack is empty");
    }

}

char stackPeek(struct stackObj *s){

    if (s->topOfStack != 0){
        return (s->stack[(s->topOfStack)-1]);
    } else {
        return '`';
    }

}

int stackIsEmpty(struct stackObj *s){

    if (s->topOfStack==0) {
        return 1;
    } else {
        return 0;
    }

}

int stackIsFull(struct stackObj *s){

    if (s->topOfStack==MAX) {
        return 1;
    } else {
        return 0;
    }

}

Answer 1

在你正在做的stackPop()函数中

 s->topOfStack = s->topOfStack-1;
 return s->stack[s->topOfStack-1];

应该是

 s->topOfStack = s->topOfStack-1;
 return s->stack[s->topOfStack];

您实际上返回的是 s->stack[s->topOfStack-2]。