4.从中缀向后缀转换表达式

目录

题目

输入

输出

思路

注意事项

C++完整代码

---

题目

问题描述

　　中缀表达式就是我们通常所书写的数学表达式，后缀表达式也称为逆波兰表达式，在编译程序对我们书写的程序中的表达式进行语法检查时，往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的算术表达式转换成后缀表示，例如，将中缀表达式

(A 一 (B*C 十 D)*E) ／ (F 十 G )

转换为后缀表示为：

ABC*D十E*--FG十／

注意：为了简化编程实现，假定变量名均为单个字母，运算符只有＋，－，＊，／ 和＾（指数运算），可以处理圆括号（），并假定输入的算术表达式正确。

要求：使用栈数据结构实现 ，输入的中缀表达式以＃号结束

输入

整数N。表示下面有N个中缀表达式
N个由单个字母和运算符构成的表达式

输出

N个后缀表达式。

---

思路

1. 遍历中缀表达式的每个字符。
2. 如果当前字符是字母，直接将其添加到后缀表达式中。
3. 如果当前字符是左括号或指数运算符（^），直接入栈。
4. 如果当前字符是右括号，将栈中的运算符出栈并添加到后缀表达式中，直到遇到左括号为止。然后再将左括号出栈。
5. 如果当前字符是运算符，将栈中的运算符出栈并添加到后缀表达式中，直到栈为空或栈顶元素为左括号，或当前运算符的优先级小于等于栈顶运算符的优先级。然后将当前运算符入栈。
6. 遍历完中缀表达式后，将栈中剩余的运算符全部出栈并添加到后缀表达式中。

---

 

注意事项

1. 代码中使用了函数 isOperator 来判断一个字符是否是运算符，以及函数 getPrecedence 来获取运算符的优先级。
2. 代码使用了 stack 类来实现栈的功能，用于存储运算符。
3. 在读取中缀表达式之前，需要先读取要转换的中缀表达式的个数，并且在每次读取中缀表达式后要忽略换行符。
4. 代码中使用了 getline(cin, infix, '#') 来以 '#' 作为结束符读取中缀表达式。

5. 左括号和指数运算符在中缀表达式转换为后缀表达式的过程中具有不同的特殊性质，因此它们在处理时需要特殊对待。

   ①左括号：
   左括号在中缀表达式中用于标识一个子表达式的开始，它的作用是改变运算符的优先级。在中缀表达式转换为后缀表达式的过程中，左括号在遇到右括号之前应该保留在栈中，以确保对应的子表达式被正确处理。因此，左括号在遇到时直接入栈。

   ②指数运算符（^）：
   指数运算符在运算符中具有最高的优先级，它通常是右结合的（即指数运算符之间按照右结合的顺序进行运算）。为了在后缀表达式中正确表示指数运算符的运算顺序，我们需要将指数运算符与其他运算符区分开来，并确保它们在计算顺序上的正确性。因此，指数运算符在遇到时也直接入栈。

   总之，左括号和指数运算符在中缀表达式转换为后缀表达式的过程中需要被特殊处理，它们需要优先级高于其他运算符，并在栈中保持相对应的位置，以确保后续的处理和计算的正确性。

6. 注意处理右括号时，需要将栈中的运算符依次出栈并添加到后缀表达式中，直到遇到左括号。
7. 在最终输出后缀表达式之前，要将栈中剩余的运算符全部出栈并添加到后缀表达式中。

---

C++完整代码

#include 
#include 
#include 
using namespace std;
 
// 判断字符是否是运算符
bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
 
// 获取运算符的优先级
int getPrecedence(char c) {
    if (c == '^') {
        return 3;
    }
    else if (c == '*' || c == '/') {
        return 2;
    }
    else if (c == '+' || c == '-') {
        return 1;
    }
}
 
// 将中缀表达式转换为后缀表达式
string infixToPostfix(const string& infix) {
    stack<char> stk; // 用于存储运算符的栈
    string postfix; // 存储后缀表达式的字符串
 
    for (char c : infix) {
        if (isalpha(c)) { // 判断是否为字母
            postfix += c; // 将字母直接添加到后缀表达式中
        }
        else if (c == '(' || c == '^') { // 左括号和指数运算符直接入栈
            stk.push(c);
        }
        else if (c == ')') { // 遇到右括号时，将栈中的运算符出栈并添加到后缀表达式中，直到遇到左括号为止
            while (!stk.empty() && stk.top() != '(') {
                postfix += stk.top();
                stk.pop();
            }
            stk.pop(); // 弹出左括号
        }
        else if (isOperator(c)) { // 如果是运算符
            while (!stk.empty() && stk.top() != '(' && getPrecedence(c) <= getPrecedence(stk.top())) {
                // 当栈不为空，栈顶元素不是左括号，并且当前运算符的优先级小于等于栈顶运算符的优先级时
                postfix += stk.top(); // 将栈顶运算符出栈并添加到后缀表达式中
                stk.pop();
            }
            stk.push(c); // 当前运算符入栈
        }
    }
 
    // 将栈中剩余的运算符全部出栈并添加到后缀表达式中
    while (!stk.empty()) {
        postfix += stk.top();
        stk.pop();
    }
 
    return postfix;
}
 
int main() {
    int N;
    cin >> N; // 输入要转换的中缀表达式的个数
 
    for (int i = 0; i < N; i++) {
        string infix;
        getline(cin, infix, '#'); // 以'#'作为结束符，读取中缀表达式
        cin.ignore(); // 忽略读取中缀表达式后的换行符
        string postfix = infixToPostfix(infix); // 调用函数将中缀表达式转换为后缀表达式
        cout << postfix << endl; // 输出后缀表达式
    }
 
    return 0;
}