0

我正在解决一个练习，其中一个函数必须将中缀表示法转换为后缀表示法。下面是我的整个代码

#include<stdio.h>
#define MAX 100
char stack[MAX];
int top;
void compact(char Descomp[], char Compac[]);
void init_stack();
int push(char Elem);
int desempilha(char *Elem);
int priority(char Operator);
int arity(char Exp[], int position);
int translate_pos(char exp[], char exp_pos[]);
int main()
    {
        char Exp[MAX]; /* stores the expression read from stdin */
            char Exp_compact[MAX]; /* stores expression without spaces */
            char Exp_pos[MAX]; /* stores the expression after the translation for postfix*/
            int indicator; /* indicate if an error occurred, 0 for NO ERROR and -1 for ERROR*/
            indicator = 0;
            printf("\nType the expression: ");
            gets(Exp);
            compact(Exp, Exp_compact);
            indicator = translate_pos(Exp_compact, Exp_pos);
            puts(Exp_pos);
            return indicator;
        }
/* compact function delete spaces within the expression read from stdin */
void compact(char Descomp[], char Compac[])
        {
            int i;
            int j;
            i = 0;
            j = 0;
            while(Descomp[j] != '\0')
                {
                    if(Descomp[j] != ' ')
                        {
                            Compac[i] = Descomp[j];
                            i++;
                        }
                    j++;
                }
        }
/* initiate the stack by setting top = -1 */
void init_stack()
        {
            top = -1;
        }
/* puts the element Elem in the stack */
int push(char Elem)
        {
            if(top == MAX - 1) /* Stack is full */
                return -1;
            top++;
            stack[top] = Elem;
            return 0;
        }
/* remove the element in stack[top] and puts it in &Elem*/
int pop(char *Elem)
        {
            if(top == -1) /* stack is empty */
                return -1;
            *Elem = stack[top];
            top--;
            return 0;
        }
/* Return the priority of an operator */
int priority(char Operator)
        {
            switch(Operator)
                {
                    case '+': return 1;
                    case '-': return 1;
                    case '*': return 2;
                    case '/': return 2;
                    case '^': return 3;
                    case '(': return 4;
                    case ')': return 5;
                    default : return 0; 
                }
        }
/* returns the arity of CONSTANTS + - * / and ^, for ( an ) is merely symbolic */
int arity(char Exp[], int position)
        {
            if(priority(Exp[position]) == 1)
                {
                    if( (position == 0) || ( (priority(Exp[position - 1]) >= 1) && (priority(Exp[position - 1]) <= 3) ))
                        return 1;
                    else
                        return 2;
                }
            else if( (priority(Exp[position]) > 1) && (priority(Exp[position]) <= 4))
                return 2;
            else
                return priority(Exp[position]);
        }
/* reads an infix expression and returns postfix expression */ 
int translate_pos(char exp[], char exp_pos[])
        {
            int i;
            int j;
            int ind;
            char trash;
            i = 0;
            j = 0;
            ind = 0;
            trash = ' ';
                    init_stack();
            while(exp[i]!= '\0')
                {
                    if(arity(exp, i) == 0)
                        {
                            exp_pos[j] = exp[i];
                            j++;
                        }
                    if(arity(exp, i) == 1)
                        {
                            switch(exp[i])
                                {
                                    case '-': 
                                        {
                                            exp_pos[j] = exp_pos[i];
                                            j++;
                                        }
                                    case '+': trash = exp_pos[i];
                                }
                        }
                    if(arity(exp, i) == 2)
                        {
                            while((top != -1) && (priority(stack[top]) <= priority(exp[i])))
                                {
                                    ind = pop(&exp_pos[j]);
                                    j++;
                                }
                            ind = push(exp[i]);
                        }
                    if(priority(exp[i]) == 4)
                        {
                            ind = push(exp[i]);
                        }
                    if(priority(exp[i]) == 5)
                        {
                            while( (top != -1) && (stack[top] != '('))
                                {
                                    ind = pop(&exp_pos[j]);
                                    j++;
                                }
                            if(stack[top] == '(')
                                ind = pop(&trash);
                        }
                    i++;
                }
            while(top != -1)
                {
                    ind = pop(&exp_pos[j]);
                    j++;
                }
            return ind;

    }

我用来翻译表达式的算法是

while there is token to be read;
read the token;
if token is a constant
    push it to Exp_Postfix;
if token is '('
    push it to stack
if token is ')'
    pop from the stack all symbols until '(' be find and remove '(' from the stack
if token is an operator and its arity is 2
    pop all operators with less or equal priority than the token and store then in the Exp_Postfix;
    push token to the stack;
if token is an operator and its arity is 1
    if token is '-'
          push it to Exp_postfix;
    if token is '+'
          pass to the next token;
pop all remaining symbols in the stack and push then, in order, to the Exp_Postfix;

我编译了 .c 存档使用

gcc -Wall archive.c -o archive

并执行它。我给表情

5+(6*9^14)

它返回的表达式是

5

如果错误出现在我的代码中或问题的解决方案中，我现在不这样做。

4

1 回答 1

3

这里有很多问题，例如：

  1. compact()并分别translate_pos()离开Exp_compact和Exp_pos，没有终止\0，因此您将打印出垃圾。

  2. 您的arity()函数正在返回2一个左括号。

  3. 在 的第一个switch语句中translate_pos()，您缺少break语句。

  4. translate_pos()您在arity 为 2 时的优先级比较是从后到前。

  5. 当您比较运算符优先级时，您应该特别对待左括号，因为它在堆栈顶部时应该具有最低优先级。

  6. 你应该有更多的else关键字translate_pos()。

  7. 您正在使用gets()，它总是很糟糕，现在实际上已从 C 中删除。

我没有对它进行详尽的测试，但这里有一个正确的版本，似乎适用于我尝试过的所有测试输入：

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


/*  Function prototypes  */

void compact(char Descomp[], char Compac[]);
void init_stack();
int push(char Elem);
int desempilha(char *Elem);
int priority(char Operator);
int arity(char Exp[], int position);
int translate_pos(char exp[], char exp_pos[]);


/*  Stack variables  */

#define MAX 100
char stack[MAX];
int top;


int main(void) {
    char Exp[MAX];
    char Exp_compact[MAX] = {0};
    char Exp_pos[MAX] = {0};
    int indicator = 0;

    printf("\nType the expression: ");
    fgets(Exp, MAX, stdin);
    compact(Exp, Exp_compact);

    indicator = translate_pos(Exp_compact, Exp_pos);
    puts(Exp_pos);
    return indicator;
}


/* compact function delete spaces within the expression read from stdin */

void compact(char Descomp[], char Compac[]) {
    int i = 0;
    int j = 0;

    while ( Descomp[j] ) {
        if ( !isspace(Descomp[j]) ) {
            Compac[i++] = Descomp[j];
        }
        j++;
    }
}


/* initiate the stack by setting top = -1 */

void init_stack() {
    top = -1;
}


/* puts the element Elem in the stack */

int push(char Elem) {
    if (top == MAX - 1)         /* Stack is full */
        return -1;
    stack[++top] = Elem;
    return 0;
}


/* remove the element in stack[top] and puts it in &Elem*/

int pop(char *Elem) {
    if (top == -1)              /* stack is empty */
        return -1;
    *Elem = stack[top--];
    return 0;
}


/* Return the priority of an operator */

int priority(char Operator) {
    switch (Operator) {
        case '+':
            return 1;
        case '-':
            return 1;
        case '*':
            return 2;
        case '/':
            return 2;
        case '^':
            return 3;
        case '(':
            return 4;
        case ')':
            return 5;
        default:
            return 0;
    }
}


/* returns the arity of OPERATORS + - * / and ^,
 * for ( an ) is merely symbolic */

int arity(char Exp[], int position) {
    if ( priority(Exp[position]) == 1 ) {
        if ( (position == 0) ||
             ((priority(Exp[position - 1]) >= 1) &&
              (priority(Exp[position - 1]) <= 3)) ) {
            return 1;
        } else {
            return 2;
        }
    } else if ( (priority(Exp[position]) > 1) &&
                (priority(Exp[position]) <= 3) ) {
        return 2;
    } else {
        return priority(Exp[position]);
    }
}


/* reads an infix expression and returns postfix expression */

int translate_pos(char exp[], char exp_pos[]) {
    int i = 0, j = 0, ind = 0;
    char trash = ' ';

    init_stack();

    while ( exp[i] ) {
        if ( arity(exp, i) == 0 ) {
            exp_pos[j++] = exp[i];
        } else if ( arity(exp, i) == 1 ) {
            switch (exp[i]) {
                case '-':
                    exp_pos[j++] = exp[i];
                    break;
                case '+':
                    trash = exp_pos[i];
                    break;
                default:
                    assert(0);
            }
        } else if (arity(exp, i) == 2) {
            while ( (top != -1) &&
                    (priority(stack[top]) >= priority(exp[i])) &&
                    stack[top] != '(' ) {
                ind = pop(&exp_pos[j++]);
            }
            ind = push(exp[i]);
        } else if ( priority(exp[i]) == 4 ) {
            ind = push(exp[i]);
        } else if ( priority(exp[i]) == 5 ) {
            while ( (top != -1) && (stack[top] != '(') ) {
                ind = pop(&exp_pos[j++]);
            }
            if ( (top != - 1) && stack[top] == '(') {
                ind = pop(&trash);
            }
        }
        i++;
    }

    while (top != -1) {
        ind = pop(&exp_pos[j++]);
    }

    return ind;
}

为各种测试用例提供以下输出：

paul@local:~/src/c/postfix$ ./postfix

Type the expression: 1+2
12+
paul@local:~/src/c/postfix$ ./postfix

Type the expression: (1+2)
12+
paul@local:~/src/c/postfix$ ./postfix

Type the expression: 1+2*3
123*+
paul@local:~/src/c/postfix$ ./postfix

Type the expression: (1+2)*3
12+3*
paul@local:~/src/c/postfix$ ./postfix

Type the expression: (3+4)*4/2
34+4*2/
paul@local:~/src/c/postfix$ ./postfix

Type the expression: 5+(6*9^14)
56914^*+
paul@local:~/src/c/postfix$

我建议将我的代码与您的代码进行比较，并尝试了解个体差异以了解您哪里出错了。

于 2013-09-26T23:12:20.397 回答