中缀表达式转后缀表达式：C语言实现与详细示例

这篇文章将介绍如何使用C语言编写程序，将中缀表达式转换为后缀表达式。

什么是中缀表达式和后缀表达式？

中缀表达式是我们常见的算术表达式，其中运算符位于操作数之间。例如：A + B * C。

后缀表达式，也称为逆波兰表示法，是一种不需要括号的数学表达式。运算符位于操作数之后。例如，A + B * C 的后缀表达式为 A B C * +。

算法

初始化: 创建一个空栈和一个空字符串用于存储后缀表达式。2. 扫描中缀表达式: 从左到右扫描中缀表达式中的每个字符。 * 如果字符是操作数, 将其添加到后缀表达式字符串中。 * 如果字符是左括号 (, 将其压入栈中。 * 如果字符是右括号 ), 则从栈中弹出运算符并将其添加到后缀表达式字符串中，直到遇到左括号。弹出左括号但不添加到后缀表达式中。 * 如果字符是运算符, 比较其优先级与栈顶运算符的优先级: * 如果栈为空或栈顶运算符是左括号，则将该运算符压入栈中。 * 如果该运算符的优先级高于栈顶运算符，则将该运算符压入栈中。 * 如果该运算符的优先级等于或低于栈顶运算符，则从栈中弹出运算符并将其添加到后缀表达式字符串中，直到遇到优先级较低的运算符或左括号。然后，将该运算符压入栈中。3. 弹出剩余运算符: 扫描完中缀表达式后，将栈中剩余的运算符依次弹出并添加到后缀表达式字符串中。

C语言代码c#include <stdio.h>#include <stdlib.h>#include <ctype.h>

typedef struct { char* array; int top; int capacity;} Stack;

void initStack(Stack* stack, int capacity) { stack->array = (char*)malloc(sizeof(char) * capacity); stack->top = -1; stack->capacity = capacity;}

int isStackEmpty(Stack* stack) { return stack->top == -1;}

void push(Stack* stack, char data) { stack->top++; stack->array[stack->top] = data;}

char pop(Stack* stack) { if (isStackEmpty(stack)) { printf('Error: Stack is empty. '); exit(1); } char data = stack->array[stack->top]; stack->top--; return data;}

char peek(Stack* stack) { if (isStackEmpty(stack)) { printf('Error: Stack is empty. '); exit(1); } return stack->array[stack->top];}

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

void infixToPostfix(char* infixExpression, char* postfixExpression) { int i, j; Stack stack; initStack(&stack, 100);

for (i = 0, j = 0; infixExpression[i] != '�'; i++) {        char c = infixExpression[i];

    if (isalpha(c)) {            postfixExpression[j++] = c;        } else if (c == '(') {            push(&stack, c);        } else if (c == ')') {            while (!isStackEmpty(&stack) && peek(&stack) != '(') {                postfixExpression[j++] = pop(&stack);            }            if (isStackEmpty(&stack) || peek(&stack) != '(') {                printf('Error: Mismatched parentheses.

'); exit(1); } pop(&stack); } else if (c == '+' || c == '-' || c == '*' || c == '/') { while (!isStackEmpty(&stack) && peek(&stack) != '(' && getPrecedence(c) <= getPrecedence(peek(&stack))) { postfixExpression[j++] = pop(&stack); } push(&stack, c); } }

while (!isStackEmpty(&stack)) {        if (peek(&stack) == '(') {            printf('Error: Mismatched parentheses.

'); exit(1); } postfixExpression[j++] = pop(&stack); }

postfixExpression[j] = '�';}

int main() { char infixExpression[100]; char postfixExpression[100];

printf('请输入中缀表达式：');    scanf('%s', infixExpression);

infixToPostfix(infixExpression, postfixExpression);

printf('后缀表达式为：%s

', postfixExpression);

return 0;}

示例

输入: A+B*C-D/E

输出: ABC*+DE/-

总结

本文介绍了使用C语言实现中缀表达式到后缀表达式的转换方法。该算法利用栈数据结构来处理运算符的优先级和括号。理解该算法可以帮助您更好地理解编译器和解释器的工作原理。