|
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
数据结构：用到了两个堆栈S1,S2
算法：一个个扫描，遇到数字的时候入栈S2
?【遇到数字】需要处理带正负符号的数字以及带小数点的小数 :带正负符号的数字，则有两种情况：一个是开头出现的符号，另一个是符号的前一位是左括号；带小数点的数字，我们需要检查它的后一位是否带的小数点.
?【遇到运算符】的时候分情况：
?情况1：S1空堆或者S1栈顶元素是( 直接入
?情况2：优先级比较大也是直接入栈S1
?情况3：优先级比较小的时候不入栈S1,把S1弹出 压入S2,直到前面的两种情况发生为止?
?【遇到括号】的时候；左括号压入S1；
??右括号的时候比较复杂-> 扫描S1 一直弹出S1 并且压入S2，直到S1的左括号为止,把S1中的左括号废弃掉
? 【最后一步】：退出扫描以后，把S1剩余的全部压入S2??
ps:这题的情况是真的多。。。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct pheap{
char data[50];
int top;
}heap;
int isEmpty(heap *H)//是否空
{
if(H->top==-1)return 1;
return 0;
}
void add(heap *H,char x)//入栈
{
H->data[++H->top]=x;
}
char pop(heap *H)//出栈
{
return H->data[H->top--];
}
int Big(char a,char b){//注意括号也要比较优先级 ，此函数若第一个参数优先级大，返回1
if((a=='*'&&(b=='+'||b=='-'))||(a=='/'&&(b=='+'||b=='-'))||b=='(')
return 1;
else return 0;
}
int isnumber(char a)
{
if(a>=48&&a<=57)return 1;
return 0;
}
int get(int start,int *next,char *token,char *str)
{
int i,j=0;
//无符号的时候
if(isnumber(str[start]))
{
for(i=start;isnumber(str[i])||str[i]=='.';i++)
{
token[j++]=str[i];
}
token[j]='\0';
*next=i;
return 1;
}
//有符号,两种情况;最开头的时候，或者前一位是括号
else if((str[start]=='+'||str[start]=='-') && (start==0||str[start-1]=='('))
{
if(str[start]=='-')
{
token[0]='-';
j=1;
}
else
j=0;
for(i=start+1;isnumber(str[i])||str[i]=='.';i++)
{
token[j++]=str[i];
}
token[j]='\0';
*next=i;
return 1;
}
else
{
token[0]=str[start];
token[1]='\0';
*next=start+1;
return 0;
}
}
int main()
{
int i,j=0,next,start=0;
char str[100],token[100];
heap *S1,*S2;
S1=(heap*)malloc(sizeof(heap));S2=(heap*)malloc(sizeof(heap));//S1储存运算符,S2储存运算数
S1->top=S2->top=-1;
S1->data[S1->top]=S2->data[S2->top]='\0';
gets(str);
for(i=0;i<strlen(str);i=next)
{
int isnum=get(i,&next,token,str);
//是数字的话入栈S2
if(isnum)
{
for(j=0;token[j]!='\0';j++)
{
add(S2,token[j]);
}
add(S2,' ');
}
//是运算符
else if(str[i]!='('&&str[i]!=')')
{
while(1){
if(isEmpty(S1)||S1->data[S1->top]=='(')
{
add(S1,str[i]);
break;
}
else if(Big(str[i],S1->data[S1->top]))
{
add(S1,str[i]);
break;
}
else
{
add(S2,pop(S1));
add(S2,' ');
}
}
}
//是左右括号
else
{
if(str[i]=='(')
{
add(S1,str[i]);
}
else if(str[i]==')')
{
while(S1->data[S1->top]!='(')
{
add(S2,pop(S1));
add(S2,' ');
}
pop(S1);//把左括号废弃掉
}
}
}
while(!isEmpty(S1))
{
add(S2,pop(S1));
add(S2,' ');
}
pop(S2);
for(i=0;i<=S2->top;i++)
{
printf("%c",S2->data[i]);
}
return 0;
}
|