中缀表达式转后缀c++栈

思路：

1.如果当前字符是数字，则直接输出。

2.如果当前字符是左括号，将其压入栈中。

3.如果当前字符是右括号，则将栈顶元素弹出并输出，直到遇到左括号，左括号不输出。

4.如果当前字符是运算符，若其优先级高于栈顶运算符，则将其压入栈中；否则将栈顶运算符弹出并输出，直到当前运算符优先级高于栈顶运算符优先级为止，然后将当前运算符压入栈中。

5.最后将栈中剩余的运算符依次弹出并输出。

代码实现：

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>

#define MAXSIZE 100

int priority(char op) { // 定义运算符优先级，数字越大优先级越高
    if (op == '*' || op == '/') {
        return 2;
    } else if (op == '+' || op == '-') {
        return 1;
    } else {
        return 0; // 左括号的优先级最低
    }
}

void infix2postfix(char *infix, char *postfix) {
    char stack[MAXSIZE]; // 运算符栈
    int top = -1; // 栈顶指针初始化为-1
    int len = strlen(infix); // 中缀表达式长度
    int j = 0; // 后缀表达式下标

    for (int i = 0; i < len; i++) {
        if (isdigit(infix[i])) { // 如果当前字符是数字，则直接输出到后缀表达式中
            postfix[j++] = infix[i];
        } else if (infix[i] == '(') { // 如果当前字符是左括号，则将其压入栈中
            stack[++top] = infix[i];
        } else if (infix[i] == ')') { // 如果当前字符是右括号，则将栈顶元素弹出并输出，直到遇到左括号
            while (top >= 0 && stack[top] != '(') {
                postfix[j++] = stack[top--];
            }
            if (top >= 0 && stack[top] == '(') { // 左括号不输出
                top--;
            }
        } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') { // 如果当前字符是运算符
            while (top >= 0 && priority(stack[top]) >= priority(infix[i])) { // 栈顶运算符优先级高于当前运算符，则将其弹出并输出
                postfix[j++] = stack[top--];
            }
            stack[++top] = infix[i]; // 将当前运算符压入栈中
        }
    }

    while (top >= 0) { // 将栈中剩余的运算符依次弹出并输出
        postfix[j++] = stack[top--];
    }

    postfix[j] = '\0'; // 后缀表达式结束标志
}

int main() {
    char infix[MAXSIZE], postfix[MAXSIZE];
    printf("请输入中缀表达式：");
    scanf("%s", infix);

    infix2postfix(infix, postfix);

    printf("后缀表达式为：%s\n", postfix);

    return 0;
}