Problem Description
对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。
Input
输入一个算术表达式，以‘#’字符作为结束标志。
Output
输出该表达式转换所得到的后缀式。
Example Input
a*b+(c-d/e)*f#
Example Output
ab*cde/-f*+
Think: 一道栈的题。根据题意就知道要想实现将原式改成后缀式（满足原式的计算顺序），建立一个栈显然不够，于是就一个栈来存运算数，如abc,另一个来存运算符，如+-*/（），而这个栈要在适合的时机还要进入一开始存运算数的栈（最后的归宿）。而这个入栈、出栈的时机是什么呢？小伙伴先思考思考，可以举题目里的栗子，模拟出先后顺序。。。↖(^ω^)↗
无添加的纯C代码如下，咕咚咕咚，隔~~~好喝^_^
#include<stdio.h> #include<string.h> #include<malloc.h> #define MAX 1001 //栈的大小，可以多加几个0 typedef char Elem; typedef struct { int base; int top; Elem *data; int size; }stack; //栈 void Init(stack *s); //初始化栈 void Push(stack *s, int k); //压栈（入栈） void Pop(stack *s); //出栈 int Empty(stack *s); //判断栈是否为空 int f(char a); //为了便于知道运算符的优先级，返回一个值来便于后续操作 char Gettop(stack *s); //返回栈顶元素 void Show(stack *s); //输出栈 int main() { char c, cc; stack s, t; Init(&s); //存运算数、符的栈初始化 Init(&t); //临时存运算符的栈初始化 while(scanf("%c", &c)&&c != '#'){ if(c != '+'&&c != '-'&&c != '*'&&c != '/'&&c != '('&&c != ')'){ Push(&s, c); //如果为运算数直接进入栈s } else{ //否则为运算符 if(Empty(&t)||c == '(') //如果为左括号或者临时存运算符的栈为空，直接进栈t Push(&t, c); else if(c == ')'){ while(!Empty(&t)){ //如果栈t,不为空，把栈t里在左括号后入栈的元素，从栈顶依次入栈s cc = Gettop(&t); if(cc != '('){ Push(&s, cc); Pop(&t); } else{ //如果右括号遇到左括号，那么，它俩就牵着小手离开了集体。。。 Pop(&t); break; } } } else{ //如果c是运算符*/+-，当然我们学过数学都知道*/的运算优先于+- int b = f(c); while(!Empty(&t)){ cc = Gettop(&t); int k = f(cc); if(b <= k&&k != 4){ //左括号等待的“人”只有右括号 Push(&s, cc); //如果当前运算符的优先级不大于栈t的栈顶,就要改入栈s, and从栈t出栈 Pop(&t); } else break; } Push(&t, c); //等待入栈的元素c不能忘!!! } } } while(!Empty(&t)){ //如果临时栈t,不空，就要按从栈顶到栈低的顺序依次入栈s cc = Gettop(&t); Push(&s, cc); Pop(&t); } Show(&s); //输出栈s return 0; //结束了，上面的代码是根据规律来的，一定要举个栗子，动手模拟一下这波神奇的操作，便于理解 } void Init(stack *s) { s->data = (Elem *)malloc(MAX * sizeof(Elem)); if(!s->data) exit(0); s->top = s->base = 1; s->size = MAX; } void Push(stack *s, int k) { s->data[s->top++] = k; } void Pop(stack *s) { s->top--; } int f(char a) { if(a == '(') return 4; else if(a == '*'||a == '/') return 2; else if(a == '-'||a == '+') return 1; return 0; } char Gettop(stack *s) { return s->data[s->top - 1]; } int Empty(stack *s) { if(s->top == s->base) return 1; return 0; } void Show(stack *s) { while(s->base < s->top){ printf("%c", s->data[s->base++]); } printf("\n"); }