Infix to Postfix conversion error
I am writing a basic program to convert an expression given in the infix notation to its postfix notation using a stack.
Here is my program.
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#define MAX_STACK_SIZE 100
//STACK IMPLEMENTATION BEGINS
struct stack{
int top;
char items[MAX_STACK_SIZE];
};
void push(struct stack* s, char n){
if(s->top==MAX_STACK_SIZE-1)
printf("Stack Overflow. Cannot pushn");
else
s->items[++s->top]=n;
}
bool isempty(struct stack* s){
if(size(s)==0)
return 1;
else return 0;
}
char pop(struct stack* s){
if(isempty(s))
{printf("nStack Underflow. Cannot Popn");
return 0;}
else
{return (s->items[s->top--]);
}
}
bool isfull(struct stack* s){
if(size(s)==MAX_STACK_SIZE)
return 1;
else return 0;
}
void display(struct stack* s){
int num;
if(isempty(s))
printf("Stack empty. Nothing to displayn");
else
{
for(num=0;num<=s->top;num++)
printf("%d ",s->items[num]);
}
}
int size(struct stack* s){
if(s->top==-1)
return 0;
else
return (s->top+1);
}
//STACK IMPLEMENTATION ENDS
//checks if a character entered is an operator or not
bool isOperator(char ch){
if(ch=='-'||ch=='+'||ch=='*'||ch=='/')
return true;
else
return false;
}
//checks if a character entered is an operand(0-9) or not
bool isOperand(char ch){
if(ch>=48 && ch<=57)
return true;
else
return false;
}
//decides the precedence of operators
int precedence(char ch){
if(ch=='*'||ch=='/')
return 2;
if(ch=='+'||ch=='-')
return 1;
}
void main(){
/*
/*Declarations Begin*/
char infix_exp[50],ch;
int a;
struct stack s;
s.top=-1;
/*Declarations End*/
printf("Enter your infix expressionn");
scanf("%s",&infix_exp);
for(a=0;a<strlen(infix_exp);a++)//scanning the entire array
{
if(isOperator(infix_exp[a])){
while(s.top>=0 && isOperator(s.items[s.top]))
{
if(s.items[s.top]=='('|| isempty(&s))
{
push(&s,infix_exp[a]);
}
if(isOperator(s.items[s.top])){
while((s.top--)>=0){
if(precedence(infix_exp[a])>=precedence(s.items[s.top]))
{
ch=pop(&s);
printf("%c",ch);
push(&s,infix_exp[a]);
}
else
{
push(&s,infix_exp[a]);
}}}}}
if(isOperand(infix_exp[a])){printf("%c",infix_exp[a]);}
if(infix_exp[a]=='('){push(&s,'(');}
if(infix_exp[a]==')'){
while(s.top>=0 && s.items[s.top]!='(')
{
ch=pop(&s);
printf("%c",ch);
}
pop(&s);
}}}
Here is the output.
Enter your infix expression
6+1
61
RUN FINISHED; exit value 3; real time: 4s; user: 0ms; system: 0ms
The logic I follow is this.
After the user enters his expression, the program scans each and every element. If the element is an operand, it is printed. If the element is an opening bracket, it is pushed onto the stack. If the element is a closing bracket, every element in the stack is popped out and printed till a corresponding opening bracket is encountered. If the element is an operator(checked by the isOperator() function) then the top element of the stack can be one of the three,
precedence() ) of the infix expression element is greater or equal to the precedence of the stack top element then the stack top is popped and printed.and the infix expression element is pushed. Otherwise only the infix expression element is pushed, nothing is popped. I am not able to get the operators in the output. What could be the error? I might be a trivial one, perhaps with the printing of values or it might be with my logic. Any help appreciated.
It looks like you're using the Shunting-yard algorithm, but there are a few things you're doing incorrectly.
First of all, after the meat of the algorithm runs you still have to print out the remaining contents of the stack and check for mismatched parens. As the wiki article says:
This is easy enough to add to your code, just add something like this after the for loop:
while(!isempty(&s))
{
ch = pop(&s);
if(ch == ')' || ch == '(') {
printf("nMismatched parensn");
break;
}
printf("%c",ch);
}
But this doesn't fix the problem right away, because there's another issue.
The second issue is with the case where the current input token is an operator, about this you say:
If the element is an operator(checked by the isOperator() function) then the top element of the stack can be one of the three,
This description is basically right, except that I think you got your precedence backwards, and you're only supposed to push to the output queue once at the end (as opposed to once for every element in the stack).
But your code doesn't match it.
Here's the relevant part of your code with comment annotations
//if the input token is an operator
if(isOperator(infix_exp[a]))
{
//while s isn't empty and has an operator on top
while(s.top>=0 && isOperator(s.items[s.top]))
{
//if the top element is a '(' (NEVER HAPPENS because '(' isn't an operator)
if(s.items[s.top]=='('|| isempty(&s))
{
push(&s,infix_exp[a]);
}
//If the top element is an operator (ALWAYS HAPPENS)
if(isOperator(s.items[s.top]))
{
//discard the top element of the stack, loop while there are still elements left
while((s.top--)>=0)
{
//if the top element of the stack (after the one that was discarded) has precedence
//then pop it to the output queue and push the input token to the stack
if(precedence(infix_exp[a])>=precedence(s.items[s.top]))
{
ch=pop(&s);
printf("%c",ch);
push(&s,infix_exp[a]);
}
//otherwise push the input token to the stack
else {
push(&s,infix_exp[a]);
}
}
}
}
}
Note that one of the if statements is never triggered. You have two while loops to iterate over the stacks, one of which doesn't actually do any iterating. You shrink the stack in two different places in the second while loop. And the input token could be pushed to output multiple times.
Overall it's just a big mess.
Now let's look at what the algorithm (again according to wikipedia) says to do (sorry about the sucky formatting):
If the token is an operator, o1, then:
while there is an operator token, o2, at the top of the stack, and
either o1 is left-associative and its precedence is equal to that of o2
or o1 has precedence less than that of o2,
push o1 onto the stack.
This doesn't really match the above code, but what would?
Well the first part is right
//if the input token is an operator
if(isOperator(infix_exp[a]))
{
And then you need to use a loop check to see if there's an operator at the top of the stack with the proper precedence:
//Traverse stack while the precedence is right
while(!isempty(&s) && isOperator(s.items[s.top])
&& (precedence(infix_exp[a]) <= precedence(s.items[s.top])) )
{
And pop from within the loop:
ch = pop(&s);
printf("%c",ch);
}
And finally push the input token onto the stack:
push(&s, infix_exp[a]);
}
上一篇: C堆栈字符串的问题
下一篇: 中缀到Postfix转换错误