中缀式转后缀式的时间效率

中缀式转后缀式的时间效率可以使用栈来实现，时间复杂度为 O(n)，其中 n 表示中缀式的长度。具体实现过程如下：

1. 初始化一个空栈和一个空字符串作为输出结果。
2. 从左到右遍历中缀表达式的每个元素。
3. 如果遇到操作数，将其加入输出结果中。
4. 如果遇到左括号，将其压入栈中。
5. 如果遇到右括号，将栈中的元素弹出并加入输出结果中，直到遇到左括号。左括号不加入输出结果中。
6. 如果遇到操作符，将其加入栈中。但在加入之前，需要将栈中优先级大于等于该操作符的元素弹出并加入输出结果中。
7. 遍历完中缀表达式后，如果栈中还有元素，将它们依次弹出并加入输出结果中。
8. 输出结果即为后缀表达式。

由于每个元素最多入栈一次，出栈一次，因此时间复杂度为 O(n)。

相关问题

C语言中缀式转后缀式代码

以下是C语言中缀式转后缀式的代码实现：

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

#define MAX_SIZE 100

int get_priority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
        case ')':
            return 0;
        default:
            return -1;
    }
}

void infix_to_postfix(char *infix, char *postfix) {
    int i, j, top = 0;
    char stack[MAX_SIZE], ch;
    
    for (i = 0, j = 0; infix[i] != '\0'; i++) {
        ch = infix[i];
        
        if (ch == '(') {
            stack[top++] = ch;
        } else if (ch == ')') {
            while (stack[top - 1] != '(') {
                postfix[j++] = stack[--top];
            }
            top--;
        } else if (ch >= '0' && ch <= '9') {
            postfix[j++] = ch;
        } else {
            while (top > 0 && get_priority(stack[top - 1]) >= get_priority(ch)) {
                postfix[j++] = stack[--top];
            }
            stack[top++] = ch;
        }
    }
    
    while (top > 0) {
        postfix[j++] = stack[--top];
    }
    postfix[j] = '\0';
}

int main() {
    char infix[MAX_SIZE], postfix[MAX_SIZE];
    
    printf("Enter an infix expression: ");
    gets(infix);
    
    infix_to_postfix(infix, postfix);
    
    printf("Postfix expression: %s\n", postfix);
    
    return 0;
}

该代码实现了一个简单的中缀式转后缀式的算法，可以将输入的中缀表达式转换为后缀表达式并输出。

C++中缀式转后缀式代码

下面是 C++ 实现中缀表达式转后缀表达式的代码，使用了栈来存储运算符：

#include <iostream>
#include <stack>
#include <string>

using namespace std;

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

// 判断运算符优先级
int getPriority(char op) {
    if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/')
        return 2;
    else if (op == '^')
        return 3;
    else
        return 0;
}

// 中缀表达式转后缀表达式
string infixToPostfix(string infix) {
    stack<char> s;
    string postfix;
    for (char c : infix) {
        if (isalnum(c)) {
            postfix += c;
        }
        else if (c == '(') {
            s.push(c);
        }
        else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop();  // 弹出左括号
        }
        else if (isOperator(c)) {
            while (!s.empty() && getPriority(s.top()) >= getPriority(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

int main() {
    string infix = "a+b*c-(d/e+f)*g";
    string postfix = infixToPostfix(infix);
    cout << postfix << endl;  // 输出 abc*+de/f+g*-
    return 0;
}

代码中，`isOperator` 函数用于判断字符是否为运算符，`getPriority` 函数返回运算符的优先级。`infixToPostfix` 函数从左至右遍历中缀表达式，对于每个字符进行如下操作：

- 如果是字母或数字，直接加入后缀表达式；
- 如果是左括号，入栈；
- 如果是右括号，弹出栈顶元素直到遇到左括号，弹出左括号；
- 如果是运算符，弹出栈中优先级不低于当前运算符的元素，直到遇到优先级更低的元素或栈为空，将当前运算符入栈；
- 最后，将栈中所有元素依次加入后缀表达式即可。

例如，对于中缀表达式 `a+b*c-(d/e+f)*g`，运行 `infixToPostfix` 函数后得到的后缀表达式为 `abc*+de/f+g*-`。