1.手动实现中缀转后缀
2.代码实现中缀转后缀并计算表达式结果
为了简化问题，假设算术运算符仅由加、减、乘、除4种运算符和左、右括号组成。
step1: 声明栈结构
#include <iostream> #include <string> using namespace std; #define MaxSize 100 template <class DataType> struct SeqStack { DataType data[MaxSize]; DataType *top; }; step2: 定义函数TranslateInfixExp实现中缀表达式转后缀表达式
/* 中缀表达式转后缀表达式 */ void TranslateInfixExp(string exp, string &result) { if (exp.empty()) return; // step1: 定义操作符栈并初始化栈 struct SeqStack<char> opStack; opStack.top = opStack.data; // step2: 遍历中缀表达式 char cur; for (int i = 0; i < exp.size(); i++) { cur = exp[i]; switch (cur) { // 遇到 '(' ，入栈 case '(': *(opStack.top++) = cur; break; // 遇到 ')' ，依次将栈中的运算符出栈并加入后缀表达式中，直至栈顶元素为 '(' ，'(' 出栈 case ')': while (*(opStack.top - 1) != '(') { result.push_back(*(--opStack.top)); result.push_back(' '); } opStack.top--; break; // 遇到 '+' 或 '-'，依次将优先级不低于所读运算符的栈顶元素出栈并加入后缀表达式，然后将所读运算符入栈 case '+': case '-': while ((opStack.top != opStack.data) && *(opStack.top - 1) != '(') { result.push_back(*(--opStack.top)); result.push_back(' '); } *(opStack.top++) = cur; break; // 遇到 '*' 或 '/' ，依次将优先级不低于所读运算符的栈顶元素出栈并加入后缀表达式，然后将所读运算符入栈 case '*': case '/': while ((opStack.top != opStack.data) && (*(opStack.top - 1) == '*') || (*(opStack.top - 1) == '/')) { result.push_back(*(--opStack.top)); result.push_back(' '); } *(opStack.top++) = cur; break; // 遇到数字字符，直接入栈 default: while (cur >= '0' && cur <= '9') { result.push_back(cur); cur = exp[++i]; } result.push_back(' '); i--; // 回退至后续首个尚未进行优先级判断的操作字符 break; } } // step3: 将栈内剩余元素依次出栈 while (opStack.top != opStack.data) { result.push_back(*(--opStack.top)); result.push_back(' '); } return; } 注意：
- 在将中缀表达式转后缀表达式过程中，每输出一个数字字符，需要在其后补一个空格（与其他相邻数字字符隔开），否则一连串数字字符放在一起无法区分是一个数字还是两个数字。
- 遇到数字字符入栈时，若当前运算项位数>1时，需要在当前数字字符入栈后后移一位并重复入栈（代码中switch的default段代码），并在运算项入栈完毕之后需要将索引i回退至后续首个尚未进行优先级判断的运算符上（即非数字字符）。
step3: 定义函数CaculatePostFixExp实现后缀表达式结果计算
/* 计算后缀表达式结果 */ float CaculatePostFixExp(string exp) { float result = 0; if (exp.empty()) { cout << "The expression is wrong!n"; exit(-1); } // step1 : 定义一个数据字符栈，并初始化 struct SeqStack<float> numStack; numStack.top = numStack.data; // step2 : 遍历后缀表达式 char cur; for(int i=0; i<exp.size(); i++) { cur = exp[i]; if (cur >= '0' && cur <= '9') // 若当前字符为数字字符 { float value = 0; while (cur != ' ') { value = value * 10 + cur - '0'; cur = exp[++i]; } *(numStack.top++) = value; } else if(cur != ' ') // 若当前字符是运算符（空格直接忽略） { float num1 = *(--numStack.top); float num2 = *(--numStack.top); switch (cur) { case '+': *(numStack.top++) = num2 + num1; break; case '-': *(numStack.top++) = num2 - num1; break; case '*': *(numStack.top++) = num2 * num1; break; case '/': *(numStack.top++) = num2 / num1; break; default: break; } } } // step3 : 栈中最终元素出栈，即为所求表达式的值 if (numStack.top != numStack.data) { result = *(--numStack.top); return result; } else { cout << "The expression is wrong!n"; exit(-1); } } 注意：
若当前字符为运算符且为减号'-'时，先出栈的为减数，后出栈的为被减数；对于除法'/'也一样。
step4: main函数调用
int main() { string infixExp; // 存储用户输入的中缀表达式 string postfixExp; // 存储转换后的后缀表达式 double result; // 存储后缀表达式计算机结果 cout << "Please enter an infix expression:n"; cin >> infixExp; // 6+(7-1)*3+10/2 cout << "The infix expression is: " << infixExp << endl; TranslateInfixExp(infixExp, postfixExp); cout << "The postfix expression is: " << postfixExp << endl; result = CaculatePostFixExp(postfixExp); cout << "The postfix expression calculation result is: " << result << endl; return 0; } 输出：
Please enter an infix expression: 6+(7-1)*3+10/2 The infix expression is: 6+(7-1)*3+10/2 The postfix expression is: 6 7 1 - 3 * + 10 2 / + The postfix expression calculation result is: 29 
