数据结构实验之栈二：一般算术表达式转换成后缀式
Time Limit: 1000MS Memory limit: 65536K
题目描述
对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。
输入
输入一个算术表达式，以‘#’字符作为结束标志。
输出
输出该表达式转换所得到的后缀式。
示例输入
a*b+(c-d/e)*f#
示例输出
ab*cde/-f*+
代码
#include<stdio.h>
#include<stdlib.h>
#define stackmax 10000
#define stacknum 10000
typedef struct //栈函数
{
char *top;
char *base;
int stacksize;
}stack;
int initstack(stack &s) //函数初始化
{
s.base = (char *)malloc(stackmax*sizeof(char));
if(!s.base) exit(0);
s.top = s.base;
s.stacksize = stackmax;
return 1;
}
void push(stack &s,char e) //进栈函数
{
if(s.top - s.base > s.stacksize)
{
s.base = (char *)malloc((stackmax + stacknum)*sizeof(char));
if(!s.base)exit(0);
s.top = s.base + s.stacksize;
s.stacksize += stacknum;
}
*s.top++ = e;
}
void pop(stack &s) //出栈函数
{
s.top--;
printf("%c",*s.top);
}
void choose(stack &s,char str[])
{
for(int i = 0;str[i] != '#';i++) //遍历整个字符串
{
if(str[i] >= 'a' && str[i] <= 'z') //遇到字母字节输出，排列顺序不变
{
printf("%c",str[i]);
}
else if(str[i] == '*' || str[i] == '/') //遇到* / ，优先级高，直接进栈
{
push(s,str[i]);
}
else if(str[i] == '+' || str[i] == '-') //遇到+ - ,检索是否是在栈顶的是否优先级高，
{
if(*(s.top-1) == '*' || *(s.top-1) == '/') //如果是的话输出优先级高的* 或/
{
pop(s);
}
push(s,str[i]); //然后进栈
}
else if(str[i] == '(') //遇到左括号进栈
{
push(s,str[i]);
}
else if(str[i] == ')') //遇到右括号出栈
{
while(*(s.top-1) != '(') //一直遇到左括号停止出栈
{
pop(s);
}
s.top--;
}
}
while(s.top != s.base) //输出栈内的字符
{
pop(s);
}
printf("\n");
}
int main()
{
stack s;
char str[stackmax];
gets(str);
initstack(s);
choose(s,str);
return 0;
}
转载于:https://www.cnblogs.com/CCCrunner/p/6444636.html
相关资源：JAVA上百实例源码以及开源项目
