7-2 后缀式求值c语言

后缀表达式也称为逆波兰表达式，它是一种不包含括号的算术表达式。后缀表达式的运算符在后面，每个运算符的操作数都在它前面。例如，后缀表达式 "3 4 +" 等价于中缀表达式 "3 + 4"。

后缀表达式求值可以使用栈来实现。具体步骤如下：

1. 从左到右扫描后缀表达式。

2. 如果是操作数，将其压入栈中。

3. 如果是运算符，弹出栈顶的两个操作数，进行运算，并将结果压入栈中。

4. 重复步骤 2 和步骤 3，直到表达式的最右端。

5. 最后，栈中只剩下一个元素，即为表达式的值。

以下是使用 C 语言实现后缀表达式求值的代码示例：

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

#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    int stack[MAX_STACK_SIZE];
} Stack;

void push(Stack *s, int data) {
    if (s->top >= MAX_STACK_SIZE) {
        printf("Stack overflow\n");
        exit(EXIT_FAILURE);
    }
    s->stack[++s->top] = data;
}

int pop(Stack *s) {
    if (s->top < 0) {
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return s->stack[s->top--];
}

int evaluatePostfix(char *expr) {
    Stack s;
    s.top = -1;
    int i, op1, op2, result;

    for (i = 0; expr[i] != '\0'; i++) {
        if (isdigit(expr[i])) {
            push(&s, expr[i] - '0');
        } else {
            op2 = pop(&s);
            op1 = pop(&s);
            switch (expr[i]) {
                case '+':
                    result = op1 + op2;
                    break;
                case '-':
                    result = op1 - op2;
                    break;
                case '*':
                    result = op1 * op2;
                    break;
                case '/':
                    if (op2 == 0) {
                        printf("Division by zero\n");
                        exit(EXIT_FAILURE);
                    }
                    result = op1 / op2;
                    break;
                default:
                    printf("Invalid operator\n");
                    exit(EXIT_FAILURE);
            }
            push(&s, result);
        }
    }

    result = pop(&s);

    if (s.top >= 0) {
        printf("Invalid expression\n");
        exit(EXIT_FAILURE);
    }

    return result;
}

int main() {
    char expr[MAX_STACK_SIZE];
    printf("Enter postfix expression: ");
    fgets(expr, MAX_STACK_SIZE, stdin);
    int result = evaluatePostfix(expr);
    printf("Result = %d\n", result);
    return 0;
}

在这个示例中，我们使用了一个 `Stack` 结构体来实现栈的功能。`push` 函数用于将元素压入栈中，`pop` 函数用于弹出栈顶元素。`evaluatePostfix` 函数用于计算后缀表达式的值。在函数中，我们遍历后缀表达式的每个字符，如果是数字，就将其转化为整数并压入栈中；如果是运算符，就弹出栈顶的两个操作数进行运算，并将结果压入栈中；最后，弹出栈顶元素作为表达式的值，并检查栈是否为空。