stack infix to postfix
#include<iostream>
#define MS 100
using namespace std;
typedef struct stack{
int arr[MS];
int top;
}stack;
void init(stack *pts)
{
pts->top=-1;
}
int isfull(stack *pts)
{
if(pts->top==MS-1)
{
return 1;
}
else
{
return 0;
}
}
int isempty(stack *pts)
{
if(pts->top==-1)
{
return 1;
}
else
{
return 0;
}
}
void push(stack *pts,int data)
{
if(isfull(pts))
{
return;
}
else
{
++pts->top;
pts->arr[pts->top]=data;
}
}
int pop(stack *pts)
{
int temp;
if(isempty(pts))
{
return 9999;
}
else
{
temp=pts->arr[pts->top];
--pts->top;
return temp;
}
}
int peek(stack *pts)
{
if(isempty(pts)!=1)
{
return pts->arr[pts->top];
}
}
int prcd(char ch)
{
if(ch=='*'||ch=='/'||ch=='%')
return 3;
else if(ch=='+'||ch=='-')
return 2;
else
return 1;
}
char *intopost(char ip[])
{
static char op[100];
int i,j,temp;
stack s;
init(&s);
for(i=0,j=0;ip[i]!='\0';i++)
{
if(ip[i]>='0'&&ip[i]<='9')
{
op[j++]=ip[i];
}
else
{
if(ip[i]=='(')
{
push(&s,ip[i]);
}
else if(ip[i]==')')
{
do
{
temp=pop(&s);
if(temp!='(')
{
op[j++]=temp;
}
}
while(temp!='(');
}
else
{
while(isempty(&s)!=1&&prcd(peek(&s))>=prcd(ip[i]))
{
op[j++]=pop(&s);
}
push(&s,ip[i]);
}
}
}
while(isempty(&s)!=1)
{
op[j++]=pop(&s);
}
op[j++]='\0';
return op;
}
int posteval(char ip[])
{
int i,j,temp,res,op1,op2;
stack s;
init(&s);
for(i=0;ip[i]!='\0';i++)
{
if(ip[i]>='0'&&ip[i]<='9')
{
push(&s,ip[i]-'0');
}
else
{
op1=pop(&s);
op2=pop(&s);
if(ip[i]=='+')
res=op2+op1;
else if(ip[i]=='-')
res=op2-op1;
else if(ip[i]=='*')
res=op2*op1;
else if(ip[i]=='/')
res=op2/op1;
else if(ip[i]=='%')
res=op2%op1;
push(&s,res);
}
}
return pop(&s);
}
int main()
{
char op[30];
char *p;
int n;
fgets(op,sizeof(op),stdin);
p=intopost(op);
puts(p);
n=posteval(p);
cout<<n;
}
Comments
Post a Comment