C++算法实战: 中缀表达式转后缀表达式及求值

在计算机科学中，中缀表达式是我们常用的数学表达式形式，例如 '2 + 3 * 4'。然而，对于计算机来说，处理后缀表达式（也称为逆波兰表达式）更为方便，例如 '2 3 4 * +'。

本文将介绍如何使用C++将中缀表达式转换为后缀表达式，并对后缀表达式进行求值。

1. 算法原理

1.1 中缀表达式转后缀表达式

初始化一个空栈和一个空字符串（用于存储后缀表达式）。2. 从左到右遍历中缀表达式： - 如果遇到操作数，直接将其添加到后缀表达式字符串中。 - 如果遇到左括号 '('，将其压入栈中。 - 如果遇到右括号 ')'，则不断弹出栈顶元素并添加到后缀表达式字符串中，直到遇到左括号为止（左括号也弹出但不添加到字符串中）。 - 如果遇到运算符，则将栈中优先级大于或等于当前运算符的运算符弹出并添加到后缀表达式字符串中，然后将当前运算符压入栈中。3. 遍历完中缀表达式后，将栈中剩余的运算符依次弹出并添加到后缀表达式字符串中。

1.2 后缀表达式求值

初始化一个空栈。2. 从左到右遍历后缀表达式： - 如果遇到操作数，将其转换为数值并压入栈中。 - 如果遇到运算符，则从栈中弹出两个操作数，进行相应的运算，并将结果压入栈中。3. 遍历完后缀表达式后，栈中唯一的元素即为表达式的值。

2. C++代码实现cpp#include #include #include using namespace std;

// 判断字符是否为运算符bool isOperator(char c) { return (c == '+' || c == '-' || c == '*' || c == '/');}

// 获取运算符的优先级int precedence(char c) { if (c == '*' || c == '/') return 2; else if (c == '+' || c == '-') return 1; else return 0;}

// 将中缀表达式转换为后缀表达式string infixToPostfix(string expression) { string postfix = ''; stack st;

for (int i = 0; i < expression.length(); i++) {        char c = expression[i];

    if (isOperator(c)) {            while (!st.empty() && st.top() != '(' && precedence(st.top()) >= precedence(c)) {                postfix += st.top();                st.pop();            }            st.push(c);        } else if (c == '(') {            st.push(c);        } else if (c == ')') {            while (!st.empty() && st.top() != '(') {                postfix += st.top();                st.pop();            }            st.pop(); // 弹出 '('        } else {            postfix += c;        }    }

while (!st.empty()) {        postfix += st.top();        st.pop();    }

return postfix;}

// 计算后缀表达式的值int evaluatePostfix(string postfix) { stack st;

for (int i = 0; i < postfix.length(); i++) {        char c = postfix[i];

    if (isdigit(c)) {            st.push(c - '0');        } else {            int operand2 = st.top();            st.pop();            int operand1 = st.top();            st.pop();

        switch (c) {                case '+':                    st.push(operand1 + operand2);                    break;                case '-':                    st.push(operand1 - operand2);                    break;                case '*':                    st.push(operand1 * operand2);                    break;                case '/':                    st.push(operand1 / operand2);                    break;            }        }    }

return st.top();}

int main() { int n; cin >> n;

while (n--) {        string expression;        cin >> expression;

    string postfix = infixToPostfix(expression);        int result = evaluatePostfix(postfix);

    cout << postfix << ' ' << result << endl;    }

return 0;}

3. 示例

输入：

62+43+272(4+6)(5/2+4)5+2(3+5)(7-2)/45*(8-(3+2))

输出：

24+ 6327*+ 17246+* 2052/4+5*2+ 3235+72-4/ 105832+- 15

4. 总结

本文介绍了如何使用C++实现中缀表达式到后缀表达式的转换，并对后缀表达式进行求值。通过理解算法原理和代码实现，你可以更加灵活地处理不同类型的表达式求值问题。