算术表达式的转换
Time Limit: 1000MS Memory limit: 65536K
题目描述
小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。 因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。输入
输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）输出
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。示例输入
a*b+(c-d/e)*f#
示例输出
+*ab*-c/def
a*b+c-d/e*f
ab*cde/-f*+
///这道题真是刻苦铭心啊233333卡了好长时间的....
///后缀表达式前面有 才改的...
///中缀表达式就是把括号去掉...木有问题...
///前缀跟后缀差不多 但是前缀需要运算符栈(s)和数字栈(num)
///主要思路 ： i. 栈外元素优先级（仅限于运算符号比较且设括号优先级最低）高于等于s栈顶元素 栈外元素进s栈 ii. 低于时 while() :s栈顶元素出栈压入num栈,一直到 i. 成立;
///中缀转化为前缀表达式步骤如下（字符数组逆序读入）
///1.如果字符数组读入是数字符号 压入num栈for(;;) ：step1~5
///2.如果读入是右括号或者s栈空 压入s栈
///3.如果读入是左括号 3-1 while() ：s 元素出栈 并且压入num栈 直至s栈顶右括号 3-2 舍弃右括号
///4.如果读入是 + 或者 - ：只要s栈顶不是括号是其他的运算符(* / ) ：while() ：s栈顶元素出栈压入num栈;一直到s栈顶是括号后栈外元素压入s栈
///5.如果读入是 * 或者 / ：直接压入s栈
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int maxsize = 10000;
typedef struct Stack
{
int Size;
char *top,*base;///equal char base[]
} Stack;
bool Empty(Stack &s) ///判断是否为空
{
if (s.top == s.base)
{
return 1;
}
return 0;
}
void Creat(Stack &s) ///建立空栈
{
s.base=new char[maxsize];
s.top=s.base;
s.Size=maxsize;
}
bool flag(char ch) ///判断是不是 数字符号
{
if (ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')')
{
return 0;
}
return 1;
}
void push(Stack &s,char e) ///压e入栈
{
if (s.top-s.base >= s.Size)
{
s.base=(char *)realloc(s.base,2*maxsize*sizeof(Stack)); ///防止内存不够...
s.Size+=maxsize;
}
s.top++;
*s.top=e;
}
void pop(Stack &s) ///出栈
{
if (s.top != s.base)
{
s.top--;
}
}
void print(Stack &s) ///栈打印
{
while (!Empty(s))
{
cout<<*s.top;
pop(s);
}
cout<<endl;
}
void Clear(Stack &s) ///栈清空
{
while (!Empty(s))
{
pop(s);
}
}
void last(Stack &s,char st[],int n) ///后序
{
int i;
for (i=1; i<=n; i++)
{
if (flag(st[i]))
{
cout<<st[i];
}
else
{
if (Empty(s))
{
s.top++;
*s.top=st[i];
}
else
{
if (st[i]=='(')
{
s.top++;
*s.top=st[i];
}
else if (st[i]=='+'||st[i]=='-')
{
while (*s.top=='/'||*s.top=='*'||*s.top=='+'||*s.top=='-')
{
cout<<*s.top;
pop(s);
}
push(s,st[i]);
}
else if (st[i]=='/'||st[i]=='*')
{
while (*s.top=='/'||*s.top=='*')
{
cout<<*s.top;
pop(s);
}
push(s,st[i]);
}
else if (st[i]==')')
{
while(*s.top!='(')
{
cout<<*s.top;
pop(s);
}
pop(s);
}
}
}
}
}
void pre(Stack &num,Stack &s,char st[],int n) ///前序
{
int i;
for (i=n; i>=1; i--)
{
if (flag(st[i])) ///step 1
{
push(num,st[i]);
}
else
{
if (Empty(s)) ///step 2
{
push(s,st[i]);
}
else
{
if (st[i]==')') ///step 2
{
push(s,st[i]);
}
else if (st[i]=='+'||st[i]=='-') ///step 4
{
while (*s.top=='/'||*s.top=='*')
{
push(num,*s.top);
pop(s);
}
push(s,st[i]); ///一旦跳出while则st[i]入s栈
}
else if (st[i]=='/'||st[i]=='*') ///step 5
{
push(s,st[i]);
}
else if (st[i]=='(') ///step 3
{
while(*s.top!=')')
{
push(num,*s.top);
pop(s);
}
pop(s); ///step 3-2
}
}
}
}
while (!Empty(s))
{
push(num,*s.top);
pop(s);
}
}
void mid(char s[],int n) ///中序
{
int i;
for (i=1; i<=n; i++)
{
if (s[i]!='('&&s[i]!=')')
{
cout<<s[i];
}
}
cout<<endl;
}
int main()
{
char str[maxsize],ch;
int i=0;
Stack s,num;///signal and number’s stack
Creat(s);
Creat(num);
while(ch=getchar())
{
if(ch!='#') ///以 # 作为输入结束
{
i++;
str[i]=ch;
}
else break;
}
pre(num,s,str,i); ///此时的i从1开始 i 最后为字符数组长度 即 “下标”1--i;
print(num);
mid(str,i);
Clear(s);
last(s,str,i);
print(s);
return 0;
}