逆波兰表达式计算器 - C语言实现

逆波兰表达式计算器 (C语言实现)

逆波兰表达式，也称为后缀表达式，是一种不需要括号即可表示数学表达式的记法。本文将介绍如何使用C语言实现一个简单的逆波兰表达式计算器。

算法思路

1. 使用栈存储操作数: 遍历表达式，遇到操作数则将其压入栈中。
2. 处理运算符: 遇到运算符时，从栈中弹出两个操作数，进行相应的运算，并将结果压回栈中。
3. 最终结果: 遍历完表达式后，栈顶元素即为最终计算结果。

C代码实现

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

#define MAX_SIZE 100

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

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

int pop(Stack* stack) {
    int value = stack->data[stack->top];
    stack->top--;
    return value;
}

int calculate_rpn(char* expression) {
    Stack stack;
    stack.top = -1;

    char* token = strtok(expression, ' ');
    while (token != NULL) {
        if (strcmp(token, '+') == 0) {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            push(&stack, operand1 + operand2);
        } else if (strcmp(token, '-') == 0) {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            push(&stack, operand1 - operand2);
        } else if (strcmp(token, '*') == 0) {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            push(&stack, operand1 * operand2);
        } else {
            int operand = atoi(token);
            push(&stack, operand);
        }

        token = strtok(NULL, ' ');
    }

    return pop(&stack);
}

int main() {
    char expression[MAX_SIZE];
    fgets(expression, MAX_SIZE, stdin);
    expression[strcspn(expression, '\n')] = '�';  // 移除换行符

    int result = calculate_rpn(expression);
    printf('%d\n', result);

    return 0;
}

示例

输入:

4 3 + 2 -

输出:

5

总结

本文介绍了如何使用C语言实现一个简单的逆波兰表达式计算器。通过使用栈数据结构，我们可以轻松地处理表达式的运算顺序并得到正确的结果。