Description:
In this program we have to covert the given infix expression to postfix expression and the finally evaluating that postfix expression. Here we made use of stack operations. The property of stacks is last in first out. i.e., the item that is inserted last will be the firt item remove.
ALGORITHM:
Step 1. start
Step 2. first initialize the stack to be empty
Step 3. for each character in the input string
If input string is an operand, append to the output
if the input string is a left paranthesis , push it onto the stack
else
if stack is empty or the operator has higher priority than the operator on
the topof stack or
the top of the stack is opening parenthesis
then
push the operator onto the stack
else
pop the operator from the stack and append to the output
Step 4. if the input string is a closing parenthesis , pop operators from the stack
and append the operators
to the output until an opening parenthesis is encountered. Pop the
opening parenthesis from the stack
and discard it.
Step 5. if the end of the input string is encountered , then iterate the loop until the
stack is not empty. Pop
the stack and append the remaining input string to the output.
Step 6. stop
Program:
#include<stdio.h>
#include<ctype.h>
#include<string.h>
static char str[20];
int top=-1;
main()
{
char in[20],post[20],ch;
int i,j,l;
clrscr();
printf("enter the string");
gets(in);
l=strlen(in);
for(i=0,j=0;i<l;i++)
if(isalpha(in[i]))
post[j++]=in[i];
else
{
if(in[i]=='(')
push(in[i]);
else if(in[i]==')')
while((ch=pop())!='(')
post[j++]=ch;
else
{
while(priority(in[i])<=priority(str[top]))
post[j++]=pop();
push(in[i]);
}
}
while(top!=-1)
post[j++]=pop();
post[j]='\0';
printf("\n equivalent infix to postfix is:%s",post);
getch();
}
priority (char c)
{
switch(c)
{
case'+':
case'-': return 1;
case'*':
case'/':
return 2;
case'$':
return 3;
}
return 0;
}
push(char c)
{
str[++top]=c;
}
pop()
{
return(str[top--]);
}
Input/Output:
enter the string(a+b)-(c-d)*e/f
equivalent infix to postfix is:ab+cd-e*f/-
enter the stringa+b/c*d
equivalent infix to postfix is:abc/d*+
Conclusion: the program is error free.
ii)ALGORITHM:
Step 1: Start
Step 2: Assign top=-1
Step 3: Read the input expression
Step 4: for i=0;s[i]!=’\0’ in steps of 1
Step 5: If isdigit(ch)
Step 5.1:Push(ch)
Step 6: otherwise
Step 6.1:op1=pop()
Step 6.2: op2=pop()
Step 7: c=op2+op1
Step 8: Push(c)
Step 9: c=op2-op1
Step 10: Push(c)
Step 11: c=pow(op2,op1)
Step 12: Push(c)
Step 13: c=op2/op1
Step 14:Push(c)
Step 15: Print the result
Step 16:Push(int x)
Step 17:Increment top by 1
Step 18: s1.item(s1.top3)=x
Step 19:pop()
Step 20: Read x
Step 21: x1=s1.item[s1.top]
Step 22:s1.top—
Step 23:return x
Step 24: Stop
Program:
#include<stdio.h>
#include<ctype.h>
int stk[10],top=0,op1,op2,i;
main()
{
char postexp[10];
clrscr();
printf("enter the postfix expression:");
gets(postexp);
for(i=0;postexp[i]!='\0';i++)
{
if(isdigit(postexp[i]))
push(postexp[i]-48);
else
{
op1=pop();
op2=pop();
switch(postexp[i])
{
case '+':push(op1+op2);
break;
case '-':push(op1-op2);
break;
case '*':push(op1*op2);
break;
case '/':push(op1/op2);
break;
case '%':push(op1%op2);
break;
case '.':exit();
}
}
}
printf("the result of postfixexpression is: %d",pop());
getch();
}
pop()
{
return(stk[top--]);
}
push(int x)
{
top++;
stk[top]=x;
}
Input/Output:
enter the postfix expression:234+-
the result of postfix expression is: 5
Conclusion: the program is error free.
VIVA QUESATIONS:
1) Define Stack ?
Ans: A stack is a linear data structure in which a data item is inserted and deleted at one end
2) Define data structure ?
Ans: A data structure is a collection of organized data that are related to each other
3) What are the various operation performed on the stack ?
Ans: push(), pop()
No comments:
Post a Comment