我们平常所用的标准四则运算表达式，如9+(3-1)*3+10/2叫做中缀表达式，后缀表达式为9 3 1 - 3 * + 10 2 / +，而后缀表达式更容易被计算机所理解计算，我们需要利用栈将中缀表达式转成后缀表达式。
规则：从左到右遍历中缀表达式中的每个数字和符号，遇到数字就输出，遇到符号，判断与栈顶符号的优先级，是右括号或优先级不高于栈顶符号，将栈顶元素依次出栈并输出，并将当前符号进栈，直到输出后缀表达式为止。
注：括号在后缀表达式中不出现，但括号在处理过程中是需要进栈的，当匹配到右括号时，将左括号后面的符号全部输出。
题目：
假定运算符集合为{ +、-、*、/、（、）}，利用栈将输入的中缀表达式转换成等价的后缀表达式，并输出。
输入格式:
输入一个字符串表示的中缀表达式（以“#”结束），其中每个操作数用一个小写字母表示。
输出格式:
将对应的后缀表达式输出。
输入样例:
a+b-a*((c+d)/e-f)+g#
输出样例:
ab+acd+e/f-*-g+代码如下：
#include <stdio.h>
#include <ctype.h>#define MAX 100// 定义栈的结构体
typedef struct {char data[MAX]; //数组存储字符int top; //表示栈顶的位置
} Stack;//栈初始化，将栈顶设为1，表示栈为空
void InitStack(Stack* s) {s->top = -1;
}//判空
int IsEmpty(Stack* s) {return s->top == -1;
}//入栈
int Push(Stack* s, char c) {if (s->top < MAX - 1) {s->data[++(s->top)] = c; //先压入，top+1return 1;}return 0;
}//出栈
int Pop(Stack* s, char* c) {if (!IsEmpty(s)) {*c = s->data[(s->top)--];return 1;}return 0;
}//获取栈顶元素
char GetTop(Stack* s) {if (!IsEmpty(s)) {return s->data[s->top];}return '#'; // 当栈为空时返回特殊符号
}// 定义运算符的优先级
int Priority(char op) {if (op == '*' || op == '/') {return 2;} else if (op == '+' || op == '-') {return 1;} else {return 0; // '(' 的优先级最低}
}// 中缀转后缀的主函数
void InfixToPostfix(char* expr) {Stack s;InitStack(&s);char result[MAX]; // 用于存储后缀表达式int k = 0;for (int i = 0; expr[i] != '#'; i++) {char c = expr[i];if (islower(c)) {result[k++] = c; // 如果是操作数，直接加入结果} else if (c == '(') {Push(&s, c); // 左括号直接入栈} else if (c == ')') {char top;while (Pop(&s, &top) && top != '(') {result[k++] = top; // 遇到右括号，弹出栈直到遇到左括号}} else { // 是运算符//栈顶运算符优先级>=当前运算符while (!IsEmpty(&s) && Priority(GetTop(&s)) >= Priority(c)) {char top;Pop(&s, &top);result[k++] = top; // 如果当前运算符优先级不高于栈顶运算符，弹出栈顶运算符}Push(&s, c); // 当前运算符入栈}}// 把栈中剩余的运算符弹出char top; //存储从栈中弹出的运算符while (Pop(&s, &top)) { //当栈不为空时，不断弹出栈顶元素result[k++] = top; //先将top添加到结果中，并将k增加}result[k] = '\0'; // 在字符串末尾添加了一个空字符printf("%s\n", result); // 输出后缀表达式
}int main() {char expr[MAX];scanf("%s", expr); // 输入中缀表达式InfixToPostfix(expr); // 转换为后缀表达式并输出return 0;
}
