Инфикс для постфиксного алгоритма в C
Я решаю упражнение, в котором одна из функций должна переводить инфиксную нотацию в постфиксную нотацию. Здесь следует весь мой код
#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
Я не знаю, если ошибка в моем коде или в решении проблемы.
1 ответ
Решение
Здесь очень много проблем, например:
compact()а такжеtranslate_pos()ПокидатьExp_compactа такжеExp_posсоответственно без окончания\0Таким образом, вы получаете мусор распечатан.ваш
arity()функция возвращается2для открывающей скобки.во-первых
switchзаявление оtranslate_pos(), ты пропускаешьbreakзаявления.Ваше приоритетное сравнение в
translate_pos()когда арити 2 обратно вперед.Когда вы сравниваете приоритет оператора, вы должны обращать особое внимание на открывающую скобку, так как она должна иметь самый низкий приоритет в верхней части стека.
Вы должны иметь намного больше
elseключевые слова вtranslate_pos(),Вы используете
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$
Я бы посоветовал сравнить мой код с вашим и попытаться понять индивидуальные различия, чтобы увидеть, где вы ошибаетесь.