PTA数据结构与算法题目集(中文) 7-20
7-20 表达式转换 (25 分)
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
题目分析：一开始没思路 百度一下就有了。。看了大佬的思路
一种方法是利用树的想法 将中缀表达式写成树的形式 利用先序遍历可以输出前缀表达式 利用后续遍历可以输出后缀表达式
另一种方法是利用栈的想法 可以利用栈将中缀表达式转换为前缀 后缀表达式
https://www.cnblogs.com/zxcjj/p/7793329.html先把我写的这个放在这 这个一个测试点都没过 。。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define INIFITY -65535
char Stack[];
int topOfStack = ; void Push(char op)
{
Stack[topOfStack++] = op;
} char Pop()
{
char op = Stack[--topOfStack];
return op;
} char Top()
{
if (!topOfStack)
return 'I'; //当栈顶无元素时候返回I元素
else
return Stack[topOfStack - ];
} int IsEmpty()
{
return topOfStack == ;
} int Priority(char op)
{
switch (op)
{
case '(':return -; break;
case')':return ; break;
case'+':
case'-':return ; break;
case'*':
case'/':return ; break;
case'I':return INIFITY; break; //处理栈顶无元素的情况
}
} int postFix(char Begin[],char End[],int Length)
{
int i = ;
int TrueLength = Length;
for (int j = ; j < Length; j++)
{
if (isdigit(Begin[j])||Begin[j]=='.')
End[i++] = Begin[j];
else if (Begin[j] == '(')
Push(Begin[j]);
else if (Begin[j] == ')')
{
while (Top() != '(')
End[i++] = Pop();
Pop();
TrueLength = TrueLength - ;
}
else
{
while ()
{
if (Priority(Begin[j]) > Priority(Top()))
{
Push(Begin[j]);
break;
}
else
End[i++] = Pop();
}
}
}
while (!IsEmpty())
{
End[i++] = Pop();
}
return TrueLength;
} int main()
{
char Begin[] = { }, End[] = { };
scanf("%s", Begin);
int Length=strlen(Begin);
int TrueLength=postFix(Begin, End, Length);
for (int i = ; i < TrueLength - ; i++)
printf("%c ", End[i]);
printf("%c", End[TrueLength - ]);
return ;
}
接下来是别人的写法