如何解决计算简单的后缀表达式求值？

Question

给一个后缀表达式，计算它的值。只有"+"、"-"、"*"三种运算，操作数为0-9。

输入
第一行一个正整数n，表示后缀表达式中元素的个数。

第二行一个后缀表达式。

输出
一个数，后缀表达式的值

Answer 1

要解决计算后缀表达式的值，可以使用栈来实现。具体步骤如下：

1. 创建一个空栈。
2. 从左到右遍历后缀表达式的每个元素：
   • 如果当前元素是操作数，则将其转换为整数并压入栈中。
   • 如果当前元素是运算符，则从栈中弹出两个操作数，进行相应的运算，并将结果压入栈中。
3. 遍历完后缀表达式后，栈中只会剩下一个元素，即为最终的计算结果。

以下是一个示例代码实现：

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

#define MAX_SIZE 100

typedef struct {
    int top;
    int data[MAX_SIZE];
} Stack;

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

int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack underflow\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

int evaluatePostfix(char *expression, int size) {
    Stack stack;
    stack.top = -1;

    for (int i = 0; i < size; i++) {
        if (isdigit(expression[i])) {
            push(&stack, expression[i] - '0');
        } else {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            int result;

            switch (expression[i]) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                default:
                    printf("Invalid operator\n");
                    exit(1);
            }

            push(&stack, result);
        }
    }

    return pop(&stack);
}

int main() {
    int n;
    scanf("%d", &n);

    char expression[MAX_SIZE];
    scanf("%s", expression);

    int result = evaluatePostfix(expression, n);
    printf("%d\n", result);

    return 0;
}