ONP: Transform the Expression
Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,…,z. Assume that there is only one RPN form (no expressions like a*b*c).
Input
t [the number of expressions <= 100] expression [length <= 400] [other expressions] Text grouped in [ ] does not appear in the input file.
Output
The expressions in RPN form, one per line.
Example
Input
3 (a+(b*c)) ((a+b)*(z+x)) ((a+t)*((b+(a+c))^(c+d)))
Output
abc*+ ab+zx+* at+bac++cd+^*
C++ Code
#include<stdio.h>
struct stacks{
char info;
struct stack *link;
}*start=NULL;
typedef struct stacks node;
int maxstk=10000;
int top;
void push(char);
char pop();
void push(char item)
{
if(top>maxstk)
{
return;
}
node *ptr;
ptr=(node *)malloc(sizeof(node));
ptr->info=item;
ptr->link=start;
start=ptr;
top++;
}
char pop()
{
char poped;
node *ptr;
ptr=start;
if(top==-1)
{
//printf("underflow");
return NULL;
}
poped=ptr->info;
start=ptr->link;
free(ptr);
top--;
return poped;
}
int getpriority(char t)
{
if(t=='^')
return 3;
else
if(t=='*'||t=='/')
return 2;
else
if(t=='+'||t=='-')
return 1;
else
return 0;
}
void infixtopost(char str[])
{
int ans,item,len,i=0,m=0,tttt,q=0;
char post[1000]="",tmp;
top=-1;
len=strlen(str);
while(i<len)
{
if(isalpha(str[i])||isdigit(str[i]))
{
post[m]=str[i];
m++;
}
else
if(str[i]=='^'||str[i]=='*'||str[i]=='/'||str[i]=='+'||str[i]=='-')
{
while(1)
{
tmp=pop();
if(tmp=='(')
{
push(tmp);
push(str[i]);
break;
}
else
if(getpriority(tmp)>=getpriority(str[i]))
{
post[m]=tmp;
m++;
}
else
{
push(tmp);
push(str[i]);
break;
}
}
}
else
if(str[i]=='(')
{
push(str[i]);
}
else
if(str[i]==')')
{
while(1)
{
tmp=pop();
if(tmp=='(')
break;
post[m]=tmp;
m++;
}
}
i++;
}
printf("%s",post);
}
int main(void)
{
long int test,p;
char str[500];
scanf("%ld",&test);
for(p=0;p<test-1;p++)
{
scanf("%s",&str);
infixtopost(str);
printf("\n");
}
scanf("%s",&str);
infixtopost(str);
return 0;
}
