您现在的位置是：首页 > C语言 > C#

C#

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

林雅南 2023-08-09C#

前言中缀表达式是我们日常计算中最常用的表达式形式，它采用运算符位于操作数之间的方式来表示数学运算。而后缀表达式则是一个更加方便计算机处理的表达式形式，其中运算符位于操作数之后。在本问题中，我们

前言

中缀表达式是我们日常计算中最常用的表达式形式，它采用运算符位于操作数之间的方式来表示数学运算。而后缀表达式则是一个更加方便计算机处理的表达式形式，其中运算符位于操作数之后。在本问题中，我们将使用C语言来实现将中缀表达式转换为后缀表达式的算法。

代码实现

#include 
#include 
#include 

// 定义运算符栈结构
typedef struct {
    char* data;
    int top;
    int capacity;
} OperatorStack;

// 初始化运算符栈
void initOperatorStack(OperatorStack* stack, int capacity) {
    stack->data = (char*)malloc(sizeof(char) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
}

// 判断运算符栈是否为空
int isOperatorStackEmpty(OperatorStack* stack) {
    return stack->top == -1;
}

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

// 入栈
void pushOperator(OperatorStack* stack, char ch) {
    stack->data[++stack->top] = ch;
}

// 出栈
char popOperator(OperatorStack* stack) {
    if (isOperatorStackEmpty(stack)) {
        return '\0';
    }
    return stack->data[stack->top--];
}

// 获取栈顶运算符
char peekOperator(OperatorStack* stack) {
    if (isOperatorStackEmpty(stack)) {
        return '\0';
    }
    return stack->data[stack->top];
}

// 中缀表达式转后缀表达式
char* infixToPostfix(char* infix) {
    int infixLength = strlen(infix);
    OperatorStack operatorStack;
    initOperatorStack(&operatorStack, infixLength);
    char* postfix = (char*)malloc(sizeof(char) * (infixLength + 1));
    int postfixIndex = 0;

    for (int i = 0; i < infixLength; i++) {
        if (infix[i] == ' ') {
            continue;
        } else if (isdigit(infix[i])) {
            postfix[postfixIndex++] = infix[i]; // 操作数直接输出到后缀表达式
        } else if (isOperator(infix[i])) {
            while (!isOperatorStackEmpty(&operatorStack) && peekOperator(&operatorStack) != '(' &&
                   infix[i] <= peekOperator(&operatorStack)) {
                postfix[postfixIndex++] = popOperator(&operatorStack);
            }
            pushOperator(&operatorStack, infix[i]);
        } else if (infix[i] == '(') {
            pushOperator(&operatorStack, infix[i]);
        } else if (infix[i] == ')') {
            while (!isOperatorStackEmpty(&operatorStack) && peekOperator(&operatorStack) != '(') {
                postfix[postfixIndex++] = popOperator(&operatorStack);
            }
            popOperator(&operatorStack); // 弹出左括号
        }
    }

    while (!isOperatorStackEmpty(&operatorStack)) {
        postfix[postfixIndex++] = popOperator(&operatorStack);
    }

    postfix[postfixIndex] = '\0';
    free(operatorStack.data);

    return postfix;
}

代码解释

上述代码使用了一个运算符栈来辅助中缀表达式转换为后缀表达式。定义了运算符栈的结构体，并实现了相关的栈操作函数。在中缀表达式转换的算法中，采用了扫描中缀表达式字符的方式，处理不同的情况：

如果是操作数，直接将其输出到后缀表达式；
如果是运算符，如果运算符栈不为空并且栈顶元素不是左括号，且当前运算符的优先级小于等于栈顶运算符的优先级，则将栈顶运算符弹出，并输出到后缀表达式中，重复该过程直到满足条件为止；最后将当前运算符入栈；
如果是左括号，直接入栈；
如果是右括号，将运算符栈中的运算符依次弹出并输出到后缀表达式，直到遇到左括号为止，然后将左括号弹出。

最后，将运算符栈中剩余的运算符依次弹出并输出到后缀表达式。转换完成后，返回后缀表达式字符串。