I'm working on a problem in my data structures class and I've managed to do most it in terms of implementing the algorithm and getting the core logic sorted. But one problem that I keep running into is when the expression being converted is fully surrounded by parentheses. Such as in the case of (2+2). The correct conversion to postfix would be 2 2 +. But my program will output 2 2 + (.
It does not do this for all pairs of parentheses, only in the unique case of a fully enclosed expression, meaning that something such as 1/(2+3) will be fine
For context, this implementation uses a linked queue to store the output. The functions relating to getting priority or type were given to us by the professor, and should be fine.
All I can gather right now is that at some point the lone left parentheses is getting enqueued by accident, though I fail to see any portion of the program where this could happen aside from the last cleanup that enqueues all that is left in the stack. But I tried to look into that, and despite what I did, the parentheses remains.
As a note, we are supposed to assume optimal or "perfect" input in this task, hence the lack of consideration of some edge cases and possible error-causing scenarios
As it stands, this is the function
QUEUE infix_to_postfix(char *infixstr) {
char *p = infixstr;
QUEUE queue = { 0 }; // result postfix expression in queue
STACK stack = { 0 }; // auxiliary stack
int sign = 1, num = 0;
while (*p) { // expression string traversal
if (*p == '-' && (p == infixstr || *(p - 1) == '(')) { // get the sign of an operand
sign = -1;
}
else if (get_type(*p) == 0) { // namely *p is digit character, aation: use horner’s algorithm to get the operand
num = *p - '0';
while ((*(p + 1) >= '0' && *(p + 1) <= '9')) {
num = num * 10 + *(p + 1) - '0';
p++;
}
enqueue(&queue, new_node(sign * num, 0));
sign = 1;
}
else if (get_type(*p) == 1) { // namely *p is an operator character
int current_priority = get_priority(*p);
while (stack.top != NULL && stack.top->data != '('
&& current_priority <= get_priority(stack.top->data)) {
enqueue(&queue, pop(&stack));
}
push(&stack, new_node(*p, 1));
}
else if (get_type(*p) == 2) { // *p == '(‘
push(&stack, new_node(*p, 2));
}
else if (get_type(*p) == 3) { // *p == ‘)‘
while (stack.top != NULL && stack.top->data != '(') {
enqueue(&queue, pop(&stack));
}
pop(&stack);
}
// else ignore
p++; // move to next character
}
// finally pop each node and insert it to queue
while (stack.top) {
enqueue(&queue, pop(&stack));
}
return queue;
}
Edit:
After tinkering with the code, I've found that part of the issue at least is in the line
else if (get_type(*p) == 3) { // *p == ‘)‘
while (stack.top != NULL && stack.top->data != '(') {
enqueue(&queue, pop(&stack));
}
pop(&stack);
}
For some reason in the loop it appears to enqueue the '(' character at the end, this is despite clear instructions in the loop to not proceed if the top of the stack is the left bracket.
edit 2:
Per request, I have added more parts and the main program.
Common
typedef struct node {
int data;
int type;
struct node *next;
} NODE;
NODE* new_node(int data, int type);
void clean(NODE **npp);
void display(NODE *np);
int get_type(char c);
int get_priority(char op);
Full display implementation
void display(NODE *np) {
while (np) {
if (np->type == 0)
printf("%d", np->data);
else
printf("%c", np->data);
np = np->next;
if (np)
printf(" ");
}
}
Queue
typedef struct queue {
int length;
NODE *front;
NODE *rear;
} QUEUE;
void enqueue(QUEUE *qp, NODE *np);
NODE* dequeue(QUEUE *qp);
void clean_queue(QUEUE *qp);
Enqueue implementation
void enqueue(QUEUE *qp, NODE *np) {
// your code
if (qp->rear == NULL) {
qp->front = np;
qp->rear = np;
}
else {
qp->rear->next = np;
qp->rear = np;
}
qp->length++;
return;
}
stack
void push(STACK *sp, NODE *np);
NODE* pop(STACK *sp);
void clean_stack(STACK *sp);
Pop stack
NODE* pop(STACK *sp) {
// your code
NODE *return_node;
if (sp->top == NULL) {
return NULL;
}
else {
return_node = sp->top;
sp->top = sp->top->next;
}
sp->length--;
return return_node;
}
Main. There are some other unrelated functions in here that work fine and aren't an issue for this question.
char *tests[] = { "1+2", "(1+2*3)", "1+(6/3)" };
void test_infix_to_postfix() {
printf("------------------\n");
printf("Test: infix_to_postfix\n\n");
int n = sizeof tests / sizeof *tests;
QUEUE q = { 0 };
for (int i = 0; i < n; i++) {
q = infix_to_postfix(tests[i]);
printf("infix_to_postfix(%s): ", tests[i]);
display(q.front);
clean_queue(&q);
printf("\n");
}
printf("\n");
}
int main(int argc, char *args[]) {
if (argc <= 1) {
test_infix_to_postfix();
test_evaluate_postfix();
test_evaluate_infix();
} else {
interative_exprssion(args[1]);
}
return 0;
}
The problem is that when you transfer a node from the stack to the queue, using a pop-enqueue sequence, the next field of the transferred node is still pointing to its successor in the stack. You need to clear that next pointer.
You can fix that in enqueue, by adding the assignment np->next = NULL;
The push function will not have that issue. Although you didn't provide the code for that function, it is evident that it will have an assignment like np->next = sp->top;, and so the old next field value is not bringing havoc like you had in your enqueue function.