C语言实现中缀表达式转换为后缀表达式

C语言实现中缀表达式转换为后缀表达式攻略

中缀表达式是我们通常使用的数学表达式形式，例如2 + 3 * 4。而后缀表达式（也称为逆波兰表达式）是一种不含括号的表达式形式，运算符位于操作数之后，例如2 3 4 * +。在C语言中，我们可以使用栈数据结构来实现中缀表达式转换为后缀表达式的算法。

以下是实现中缀表达式转换为后缀表达式的完整攻略：

步骤1：创建一个栈

首先，我们需要创建一个栈来存储运算符。可以使用数组来实现栈，同时需要定义一个栈顶指针来指示栈顶元素的位置。

#define MAX_SIZE 100

char stack[MAX_SIZE];
int top = -1;

步骤2：定义运算符的优先级

为了正确地转换中缀表达式为后缀表达式，我们需要定义运算符的优先级。常见的运算符优先级如下：

• (：最低优先级
• +、-：较低优先级
• *、/：较高优先级
• ^：最高优先级

int getPriority(char operator) {
    if (operator == '(')
        return 0;
    else if (operator == '+' || operator == '-')
        return 1;
    else if (operator == '*' || operator == '/')
        return 2;
    else if (operator == '^')
        return 3;
    else
        return -1; // 非法运算符
}

步骤3：遍历中缀表达式

遍历中缀表达式的每个字符，根据字符的类型执行相应的操作：

• 如果是操作数（数字），直接输出到后缀表达式。
• 如果是运算符：
• 如果栈为空或者栈顶元素是(，则将运算符入栈。
• 如果栈不为空且栈顶元素的优先级大于等于当前运算符的优先级，则将栈顶元素出栈并输出到后缀表达式，直到栈为空或者栈顶元素的优先级小于当前运算符的优先级。然后将当前运算符入栈。
• 如果当前运算符是)，则将栈顶元素出栈并输出到后缀表达式，直到遇到(为止。

void infixToPostfix(char* infix, char* postfix) {
    int i = 0;
    int j = 0;
    char ch;

    while ((ch = infix[i++]) != '\\0') {
        if (isalnum(ch)) {
            postfix[j++] = ch;
        } else if (ch == '(') {
            push(ch);
        } else if (ch == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[j++] = pop();
            }
            pop(); // 弹出'('
        } else {
            while (top != -1 && getPriority(stack[top]) >= getPriority(ch)) {
                postfix[j++] = pop();
            }
            push(ch);
        }
    }

    while (top != -1) {
        postfix[j++] = pop();
    }

    postfix[j] = '\\0';
}

步骤4：示例说明

示例1

输入：2 + 3 * 4

输出：2 3 4 * +

解释：根据算法步骤，我们依次遍历中缀表达式的每个字符。首先，将2输出到后缀表达式。然后，遇到+运算符，将其入栈。接下来，遇到3，直接输出到后缀表达式。再遇到*运算符，由于栈顶元素的优先级较低，所以将*入栈。最后，遇到4，直接输出到后缀表达式。遍历结束后，将栈中剩余的运算符依次出栈并输出到后缀表达式，得到最终结果2 3 4 * +。

示例2

输入：(2 + 3) * 4

输出：2 3 + 4 *

解释：根据算法步骤，我们依次遍历中缀表达式的每个字符。首先，遇到(，将其入栈。然后，遇到2，直接输出到后缀表达式。接下来，遇到+运算符，将其入栈。再遇到3，直接输出到后缀表达式。遍历到)时，将栈中的运算符依次出栈并输出到后缀表达式，直到遇到(为止。最后，遇到*运算符，由于栈顶元素的优先级较高，所以将*入栈。遍历结束后，将栈中剩余的运算符依次出栈并输出到后缀表达式，得到最终结果2 3 + 4 *。

以上就是C语言实现中缀表达式转换为后缀表达式的完整攻略。通过遵循上述步骤，您可以将任意中缀表达式转换为后缀表达式。