浙大版《数据结构(第2版)》题目集-习题3.11 表达式转换 (25分)
程序员文章站
2022-06-10 19:19:01
...
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。
输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
参考代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct snode *stack;
struct snode{
char ch[20];
int top;
};
stack CreateStack(); //创建堆栈
void push(stack s,char c); //入栈
char pop(stack s); //出栈
int main()
{
char ch1[150]; //用来存储符号优先级
ch1['(']=0;
ch1['+']=1;
ch1['-']=1;
ch1['*']=2;
ch1['/']=2;
char s[21]; //用来存储中缀表达式
scanf("%s",s);
int l=strlen(s);
stack st=CreateStack();
int flag=0; //该标志位用来控制格式输出
for(int i=0;i<l;i++) //遍历中缀表达式符号
{
if(s[i]=='(')
{
push(st,s[i]);
}
else if(s[i]==')')
{
char t;
t=pop(st);
while(t!='(')
{
printf(" %c",t);
t=pop(st);
}
flag=1;
}
else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')
{
if(s[i]=='+'&&(s[i-1]=='('||i==0));//如果这个+表示正号,不进行操作
else if(s[i]=='-'&&(s[i-1]=='('||i==0))//如果这个-表示负号,直接输出
{
printf("-");
}
else if(ch1[s[i]]>ch1[st->ch[st->top]]||st->top==-1)
{
push(st,s[i]);
flag=1;
}
else
{
printf(" %c",pop(st));
while(ch1[s[i]]<=ch1[st->ch[st->top]]&&st->top!=-1)
{
printf(" %c",pop(st));
}
push(st,s[i]);
flag=1;
}
}
else //运算数直接输出(包含小数.)
{
if(flag)
{
printf(" ");
flag=0;
}
printf("%c",s[i]);
}
}
while(st->top!=-1)//输出堆栈中剩余的符号
{
printf(" %c",pop(st));
}
return 0;
}
stack CreateStack()
{
stack s=(stack)malloc(sizeof(struct snode));
s->top=-1;
return s;
}
void push(stack s,char c)
{
(s->top)++;
s->ch[s->top]=c;
}
char pop(stack s)
{
return s->ch[(s->top)--];
}
思路:
这题代码我是参考中国大学MOOC.数据结构(浙江大学)[1] 中所讲解的思路去写的,但是在一些细节处理上会更具体些,细节方面可以看代码注释,这里附上课程PPT的思路截图。
刚开始按照该思路写时,有个别测试点不通过的情况,后来参考博主damon-lin[2] 文章中的测试样例通过所有测试点,附上测试案例供参考。
序号 | 输入 | 输出 |
---|---|---|
1 | 2+3*(7-4)+8/4 | 2 3 7 4 - * + 8 4 / + |
2 | ((2+3)*4-(8+2))/5 | 2 3 + 4 * 8 2 + - 5 / |
3 | 1314+25.5*12 | 1314 25.5 12 * + |
4 | -2*(+3) | -2 3 * |
5 | 123 | 123 |
参考资料
[1]中国大学MOOC.数据结构(浙江大学): https://www.icourse163.org/learn/ZJU-93001?tid=1450069451#/learn/announce
[2]damon-lin: https://blog.csdn.net/linsheng9731/article/details/22619447
上一篇: typecho如何判断tags标签?
下一篇: PHP里的中文变量说明_php技巧