There are an awful lot of problems, here, for instance:
compact()
andtranslate_pos()
leaveExp_compact
andExp_pos
, respectively, without a terminating\0
, so you're getting garbage printed out.your
arity()
function is returning2
for an opening parenthesis.in the first
switch
statement oftranslate_pos()
, you're missingbreak
statements.Your priority comparison in
translate_pos()
when arity is 2 is back to front.When you're comparing operator precedence, you should treat an opening parenthesis specially, since it should have the lowest precedence when on the top of the stack.
You should have a lot more
else
keywords intranslate_pos()
.You're using
gets()
, which was always bad, and now has actually been removed from C.
I haven't exhaustively tested it, but here's a correct version that seems to work for all the test inputs I tried:
#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;
}
Gives the following output for various test cases:
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$
I'd suggest comparing my code to yours and trying to understand the individual differences to see where you were going wrong.