C语言中缀表达式转后缀表达式并计算：代码详解及运行步骤

C语言实现中缀表达式转后缀表达式并计算：代码详解及运行步骤

本文将详细介绍用C语言实现中缀表达式转后缀表达式并计算的代码，并提供清晰的运行步骤。

代码实现

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

// 定义栈结构
typedef struct {
    int top; // 栈顶指针
    int capacity; // 栈容量
    double* array; // 栈数组
} Stack;

// 创建栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack)); // 分配栈结构的内存空间
    stack->top = -1; // 初始化栈顶指针为-1
    stack->capacity = capacity; // 设置栈容量
    stack->array = (double*)malloc(capacity * sizeof(double)); // 分配栈数组的内存空间
    return stack; // 返回栈指针
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1; // 栈顶指针为-1表示栈为空
}

// 判断栈是否已满
int isFull(Stack* stack) {
    return stack->top == stack->capacity - 1; // 栈顶指针等于栈容量减1表示栈已满
}

// 入栈
void push(Stack* stack, double item) {
    if (isFull(stack)) { // 如果栈已满
        printf("栈已满\n"); // 输出提示信息
        return; 
    }
    stack->array[++stack->top] = item; // 栈顶指针加1，将元素放入栈顶位置
}

// 出栈
double pop(Stack* stack) {
    if (isEmpty(stack)) { // 如果栈为空
        printf("栈为空\n"); // 输出提示信息
        return -1; 
    }
    return stack->array[stack->top--]; // 返回栈顶元素，并将栈顶指针减1
}

// 获取栈顶元素
double peek(Stack* stack) {
    if (isEmpty(stack)) { // 如果栈为空
        printf("栈为空\n"); // 输出提示信息
        return -1; 
    }
    return stack->array[stack->top]; // 返回栈顶元素
}

// 判断运算符的优先级
int precedence(char op) {
    if (op == '+' || op == '-') { // 如果运算符是加号或减号
        return 1; // 返回1表示优先级为1
    } else if (op == '*' || op == '/') { // 如果运算符是乘号或除号
        return 2; // 返回2表示优先级为2
    }
    return 0; // 返回0表示优先级为0
}

// 将中缀表达式转换为后缀表达式
void infixToPostfix(char* infix, char* postfix) {
    int i, j; // 
    Stack* stack = createStack(100); // 创建容量为100的栈
    for (i = 0, j = 0; infix[i] != '\0'; i++) { // 遍历中缀表达式的每个字符
        if (isdigit(infix[i])) { // 如果字符是数字
            postfix[j++] = infix[i]; // 将数字放入后缀表达式中
        } else if (infix[i] == '(') { // 如果字符是左括号
            push(stack, infix[i]); // 入栈
        } else if (infix[i] == ')') { // 如果字符是右括号
            while (!isEmpty(stack) && peek(stack) != '(') { // 循环直到栈为空或栈顶元素为左括号
                postfix[j++] = pop(stack); // 将栈顶元素出栈并放入后缀表达式中
            }
            if (!isEmpty(stack) && peek(stack) != '(') { // 如果栈不为空且栈顶元素不为左括号
                printf("括号不匹配\n"); // 输出提示信息
                return; // 返回
            } else {
                pop(stack); // 将左括号出栈
            }
        } else { // 如果字符是运算符
            while (!isEmpty(stack) && precedence(infix[i]) <= precedence(peek(stack))) { // 循环直到栈为空或栈顶运算符优先级小于当前运算符
                postfix[j++] = pop(stack); // 将栈顶运算符出栈并放入后缀表达式中
            }
            push(stack, infix[i]); // 当前运算符入栈
        }
    }
    while (!isEmpty(stack)) { // 循环直到栈为空
        postfix[j++] = pop(stack); // 将栈顶元素出栈并放入后缀表达式中
    }
    postfix[j] = '\0'; // 后缀表达式结束符
}

// 计算后缀表达式的值
double evaluatePostfix(char* postfix) {
    int i; // 循环变量
    Stack* stack = createStack(100); // 创建容量为100的栈
    for (i = 0; postfix[i] != '\0'; i++) { // 遍历后缀表达式的每个字符
        if (isdigit(postfix[i])) { // 如果字符是数字
            push(stack, postfix[i] - '0'); // 将数字转换为整数并入栈
        } else { // 如果字符是运算符
            double operand2 = pop(stack); // 第二个操作数出栈
            double operand1 = pop(stack); // 第一个操作数出栈
            switch (postfix[i]) { // 根据运算符进行计算
                case '+': // 加法
                    push(stack, operand1 + operand2); // 将计算结果入栈
                    break;
                case '-': // 减法
                    push(stack, operand1 - operand2); // 将计算结果入栈
                    break;
                case '*': // 乘法
                    push(stack, operand1 * operand2); // 将计算结果入栈
                    break;
                case '/': // 除法
                    push(stack, operand1 / operand2); // 将计算结果入栈
                    break;
            }
        }
    }
    return pop(stack); // 返回栈顶元素，即最终计算结果
}

int main() {
    char infix[100]; // 中缀表达式
    char postfix[100]; // 后缀表达式
    printf("请输入中缀表达式：");
    scanf("%s", infix); // 输入中缀表达式
    infixToPostfix(infix, postfix); // 将中缀表达式转换为后缀表达式
    printf("后缀表达式为：%s\n", postfix); // 输出后缀表达式
    double result = evaluatePostfix(postfix); // 计算后缀表达式的值
    printf("计算结果为：%.2f\n", result); // 输出计算结果
    return 0;
}

运行步骤

1. 定义栈结构和相关函数。 代码定义了 Stack 结构体来表示栈，并定义了一系列函数来操作栈，包括创建栈、判断栈是否为空、入栈、出栈等。
2. 在主函数中声明中缀表达式和后缀表达式的字符数组。 代码在 main 函数中声明了 infix 和 postfix 数组，分别用于存储中缀表达式和后缀表达式。
3. 提示用户输入中缀表达式。 代码使用 printf 函数提示用户输入中缀表达式。
4. 读取用户输入的中缀表达式。 代码使用 scanf 函数读取用户输入的中缀表达式，并存储到 infix 数组中。
5. 调用 infixToPostfix 函数将中缀表达式转换为后缀表达式。 代码调用 infixToPostfix 函数将 infix 中存储的中缀表达式转换为后缀表达式，并将结果存储到 postfix 数组中。
6. 输出转换后的后缀表达式。 代码使用 printf 函数输出转换后的后缀表达式。
7. 调用 evaluatePostfix 函数计算后缀表达式的值。 代码调用 evaluatePostfix 函数计算 postfix 中存储的后缀表达式的值，并将结果存储在 result 变量中。
8. 输出计算结果。 代码使用 printf 函数输出计算结果。
9. 程序结束。 程序执行完毕，返回 0。

代码解析

1. 栈结构和相关函数

代码首先定义了 Stack 结构体来表示栈，包含三个成员：

• top：栈顶指针，指向栈顶元素的位置。
• capacity：栈容量，表示栈能够存储的最大元素数量。
• array：栈数组，用于存储栈元素。

代码还定义了以下函数来操作栈：

• createStack：创建栈，并返回栈指针。
• isEmpty：判断栈是否为空。
• isFull：判断栈是否已满。
• push：入栈操作。
• pop：出栈操作。
• peek：获取栈顶元素。

2. 中缀表达式转后缀表达式

infixToPostfix 函数将中缀表达式转换为后缀表达式，其核心思想是使用一个栈来存储运算符。遍历中缀表达式的每个字符，根据字符类型进行不同的处理：

• 数字：直接放入后缀表达式中。
• 左括号：入栈。
• 右括号：将栈顶元素依次出栈并放入后缀表达式中，直到遇到左括号，并将左括号出栈。
• 运算符：将栈顶优先级大于等于当前运算符的运算符出栈并放入后缀表达式中，最后将当前运算符入栈。

3. 计算后缀表达式

evaluatePostfix 函数计算后缀表达式的值，其核心思想也是使用一个栈来存储操作数。遍历后缀表达式的每个字符，根据字符类型进行不同的处理：

• 数字：将数字转换为整数并入栈。
• 运算符：将栈顶两个操作数出栈，并根据运算符进行计算，最后将计算结果入栈。

最后，栈顶元素即为后缀表达式的计算结果。

总结

本文详细介绍了用C语言实现中缀表达式转后缀表达式并计算的代码，并提供了清晰的运行步骤。代码使用了栈结构，包含创建栈、判断栈是否为空、入栈、出栈等操作，并通过优先级判断实现中缀表达式到后缀表达式的转换，最后通过栈计算后缀表达式并输出结果。该代码可以帮助你更好地理解中缀表达式转后缀表达式的算法，以及栈在算法中的应用。