【数据结构】13：表达式转换（中缀表达式转成后缀表达式）

思想：

从头到尾依次读取中缀表达式里的每个对象，对不同对象按照不同的情况处理。

1. 如果遇到空格，跳过
2. 如果遇到运算数字，直接输出
3. 如果遇到左括号，压栈
4. 如果遇到右括号，表示括号里的中缀表达式已经扫描完毕，将栈顶的运算符弹出并输出， 直至遇到左括号（左括号出栈但是不输出）
5. 若遇到运算符，若当前运算符优先级高于栈顶运算符，将其压栈； 若小于等于栈顶元素的优先级，将栈顶运算符弹出并输出，再比较新的栈顶运算符，直到该运算符优先级高于栈顶运算符优先级为止，然后将其压栈。
6. 若中缀表达式各个对象处理完毕，则把堆栈里的运算符一并输出。

示例

代码

int precedence(char op) {if (op == '+' || op == '-') return 1;else if (op == '*' || op == '/') return 2;else return 0; // 其他情况，比如括号等
}char* ExchangeToPost(char* Expr) {Stack S;S = CreateStack(100);int length = strlen(Expr);char* result = (char*)malloc(sizeof(char) * (length + 1));int i = 0;int j = 0;int k = 0;while (Expr[i] != '\0') {if (Expr[i] == ' ') {i++;}else if (isdigit(Expr[i])) {result[j] = Expr[i];//printf("case digital: result[%d]: %c\n", j, result[j]);j++;i++;}else if (Expr[i] == '(') {Push(S, Expr[i]);i++;}else if (Expr[i] == ')') {//print_s(S);char temp = Pop(S);while (temp != '(') {result[j] = temp;//printf("case ')': result[%d]: %c\n", j, result[j]);j++;temp = Pop(S);}i++;}else {if (IsEmpty(S)) {Push(S, Expr[i]);i++;continue;}char temp = Pop(S);if (temp == '(') {Push(S, temp);Push(S, Expr[i]);i++;continue;}if (precedence(Expr[i]) > precedence(temp)) {//printf("case opr: result[%d]: %c\n", j, result[j]);Push(S, temp);Push(S, Expr[i]);i++;}else {while (precedence(Expr[i]) <= precedence(temp)){result[j] = temp;//printf("case opr: result[%d]: %c\n", j, result[j]);j++;temp = Pop(S);}Push(S, temp);Push(S, Expr[i]);i++;}}//printf("i: %d, j: %d\n", i, j);//print_s(S);}while (!IsEmpty(S)) {result[j] = Pop(S);j++;}result[j] = '\0';return result;
}