Using a Stack Requirements: converts and prints the equivalent postfix expressio
ID: 3536866 • Letter: U
Question
Using a Stack
Requirements:
converts and prints the equivalent postfix expression and then evaluates the expression. The expression from the user will only contain floating point numbers, left and right parenthesis, the arithmetic operators +, -, *, / and white space.
How to Proceed:
Make sure you have the array implementation or the linked implementation of the StackADT working.
Then code the algorithm below to read in a string and convert it to postfix notation.
Finally write the main( ) driver:
The driver will combine the three pieces of the project, the stack code, the infix-to-postfix converter and the postfix evaluator (found in the textbook, chapter 3). The driver should ask the user to enter an infix expression (using spaces between each token), print the equivalent postfix expression, call the code to evaluate the postfix expression and print the value. This should continue until the user decides to stop entering expressions.
Infix to Postfix
The following is an algorithm that can be used to convert an expression in infix notation to one in postfix, or RPN. This algorithm will work on any expression that uses simple binary operators and parenthesis, things get messy with unary operators or other non-binary ones. For this example, assume we're just using +, -, *, and /
To start with, assume we've got the infix expression in a string, and that we have a stack we're going to be using to help with the conversion. All we have to do is iterate through the string, checking each character, or token. There are four scenarios (ignore any white space character):
Operator: If the token is an operator, and there's nothing else on our stack, we push that operator onto the stack. If there is something on the stack, we compare the precedence of our current operator with the one on the stack, if the stack's is greater or equal to ours, we pop it and add it to our output string. If it's less than ours, we push our current operator and go on. We keep comparing the current operator to the stack until we hit the end of the stack, we hit a left parenthesis on the stack, or we find an operator on the stack with lower precedence than ours.
Left Parenthesis: If the token is a left parenthesis we simply push it onto the stack.
Right Parenthesis: If the token is a right parenthesis, we do a Multi-Pop! That is to say, we pop everything off the stack until we hit a left parenthesis or the end of the stack.
Operand: If the token is an operand we simply add it to our output string.
When all this is done with, we perform a Super-Pop!. Which means we pop every last thing off the stack. If everything went well, then the only things left should be operators. If there's a parenthesis left over, something's wrong. If there's an operand, you've pretty seriously messed up, since at no point in the algorithm do we put those on the stack.
Explanation / Answer
#include<stdio.h>
#include<ctype.h>
#define MAX 50
typedef struct stack
{
int data[MAX];
int top;
}stack;
int precedence(char);
void init(stack *);
int empty(stack *);
int full(stack *);
int pop(stack *);
void push(stack *,int );
int top(stack *); //value of the top element
void infix_to_postfix(char infix[],char postfix[]);
void eval_postfix(char postfix[]);
int evaluate(char x,int op1,int op2);
int main()
{ char infix[30],postfix[30];
printf(" Enter an infix expression : ");
scanf("%s",infix);
infix_to_postfix(infix,postfix);
printf(" Postfix expression :%s",postfix);
printf(" Postfix evaluation : ");
eval_postfix(postfix);
return 0;
}
void infix_to_postfix(char infix[],char postfix[])
{ stack s;
char x;
int i,j;//i-index for infix[],j-index for postfix
char token;
init(&s);
j=0;
for(i=0;infix[i]!='';i++)
{ token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token == '(')
push(&s,'(');
else
if(token == ')')
while((x=pop(&s))!='(')
postfix[j++]=x;
else
{
while(precedence(token)<=precedence(top(&s)) && !empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}
}
while(!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
postfix[j]='';
}
void eval_postfix(char postfix[])
{
stack s;
char x;
int op1,op2,val,i;
init(&s);
for(i=0;postfix[i]!='';i++)
{ x=postfix[i];
if(isdigit(x))
{
push(&s,(x-'0'));
}
else
{ //pop two operands and evaluate
op2=pop(&s);
op1=pop(&s);
val=evaluate(x,op1,op2);
push(&s,val);
}
}
val=pop(&s);
printf(" value of expression = %d",val);
}
int evaluate(char x,int op1,int op2)
{
if(x=='+') return(op1+op2);
if(x=='-') return(op1-op2);
if(x=='*') return(op1*op2);
if(x=='/') return(op1/op2);
if(x=='%') return(op1%op2);
}
int precedence(char x)
{
if(x == '(') return(0);
if(x == '+' || x == '-') return(1);
if(x == '*' || x == '/' || x == '%') return(2);
return(3);
}
void init(stack *s)
{
s->top=-1;
}
int empty(stack *s)
{
if(s->top==-1) return(1);
return(0);
}
int full(stack *s)
{
if(s->top==MAX-1) return(1);
return(0);
}
void push(stack *s,int x)
{
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}
int top(stack * p)
{
return(p->data[p->top]);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.