0

関数の 1 つが中置記法を後置記法に変換する必要がある演習を解いています。ここに私のコード全体が続きます

#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_compactExp_pos\0

  2. あなたのarity()関数は2左括弧を返しています。

  3. の最初のswitchステートメントでtranslate_pos()、ステートメントが欠落していますbreak。

  4. translate_pos()アリティが 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 に答える