C语言实现中缀表达式转后缀表达式（含栈数据结构）

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

本文提供了一个使用C语言编写的程序，该程序可以将中缀表达式转换为后缀表达式，并利用栈数据结构来实现。c#include <stdio.h>#include <stdlib.h>#include <string.h>

#define MAX_SIZE 100

// 定义栈结构体typedef struct { char array[MAX_SIZE]; int top;} Stack;

// 初始化栈void initialize(Stack *s) { s->top = -1;}

// 判断栈是否为空int isEmpty(Stack *s) { return (s->top == -1);}

// 判断栈是否已满int isFull(Stack *s) { return (s->top == MAX_SIZE - 1);}

// 入栈操作void push(Stack *s, char value) { if (isFull(s)) { printf('Stack Overflow! '); exit(1); } s->array[++(s->top)] = value;}

// 出栈操作char pop(Stack *s) { if (isEmpty(s)) { printf('Stack Underflow! '); exit(1); } return s->array[(s->top)--];}

// 判断字符是否为操作数int isOperand(char ch) { return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');}

// 获取运算符的优先级int precedence(char ch) { switch (ch) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; } return -1;}

// 将中缀表达式转换为后缀表达式void infixToPostfix(char *exp) { Stack stack; initialize(&stack); int i, k;

for (i = 0, k = -1; exp[i]; ++i) {        if (isOperand(exp[i])) {            exp[++k] = exp[i];        } else if (exp[i] == '(') {            push(&stack, exp[i]);        } else if (exp[i] == ')') {            while (!isEmpty(&stack) && stack.array[stack.top] != '(') {                exp[++k] = pop(&stack);            }            if (!isEmpty(&stack) && stack.array[stack.top] != '(') {                printf('Invalid Expression!

'); exit(1); } else { pop(&stack); // 弹出左括号 } } else { // 处理运算符 while (!isEmpty(&stack) && precedence(exp[i]) <= precedence(stack.array[stack.top])) { exp[++k] = pop(&stack); } push(&stack, exp[i]); } }

// 将栈中剩余运算符弹出    while (!isEmpty(&stack)) {        exp[++k] = pop(&stack);    }    exp[++k] = '�';}

int main() { char infix[MAX_SIZE], postfix[MAX_SIZE];

printf('请输入中缀表达式: ');    fgets(infix, MAX_SIZE, stdin);

infixToPostfix(infix);    printf('后缀表达式: %s

', infix);

return 0;}

代码解释:

数据结构: 使用Stack结构体表示栈，包含一个字符数组array存储栈元素，top表示栈顶指针。2. 栈操作函数: * initialize() 初始化栈 * isEmpty() 判断栈是否为空 * isFull() 判断栈是否已满 * push() 入栈操作 * pop() 出栈操作3. 辅助函数: * isOperand() 判断字符是否为操作数 * precedence() 获取运算符的优先级，数值越大优先级越高4. 核心函数 infixToPostfix() : * 遍历中缀表达式字符串。 * 遇到操作数，直接输出到后缀表达式。 * 遇到左括号'('，入栈。 * 遇到右括号')'，将栈中元素弹出并输出到后缀表达式，直到遇到左括号'('为止（左括号不输出）。 * 遇到运算符，比较当前运算符与栈顶运算符的优先级： * 如果当前运算符优先级高于栈顶运算符，则将当前运算符入栈。 * 否则，将栈中优先级等于或高于当前运算符的运算符弹出并输出到后缀表达式，直到栈为空或遇到优先级更低的运算符，然后将当前运算符入栈。 * 遍历结束后，将栈中剩余运算符弹出并输出到后缀表达式。5. 主函数 main() : * 获取用户输入的中缀表达式。 * 调用 infixToPostfix() 函数进行转换。 * 输出转换后的后缀表达式。

注意: 这是一个简单的示例程序，可能无法处理所有情况，例如表达式中的空格、非法字符等。在实际应用中，可能需要根据具体情况进行修改和完善。