C语言中如何用栈求表达式的值

C语言中如何用栈求表达式的值

在C语言中，用栈求表达式的值的方法有：逆波兰表达式（后缀表达式）、中缀表达式转后缀表达式、栈操作的实现。其中，逆波兰表达式是最常用的方法，因为它可以简化运算符的优先级和括号处理。下面将详细描述逆波兰表达式的实现方法。

一、逆波兰表达式（后缀表达式）

逆波兰表达式是一种将操作数和操作符按一定顺序排列的表达式形式，在这种形式下，操作符总是位于操作数之后。它的优点是无需考虑运算符的优先级和括号。

1.1 逆波兰表达式的基本概念

逆波兰表达式（Reverse Polish Notation, RPN）又称后缀表达式，是一种与中缀表达式不同的表达方式。在中缀表达式中，操作符位于操作数之间，例如：

A + B

而在后缀表达式中，操作符位于操作数之后，例如：

A B +

1.2 逆波兰表达式的转换

要计算中缀表达式的值，首先需要将其转换为后缀表达式。这可以通过栈来实现。转换步骤如下：

1. 初始化一个操作符栈和一个输出队列。
2. 扫描中缀表达式的每个字符。
3. 操作数直接输出到输出队列。
4. 左括号压入栈中。
5. 右括号弹出栈中所有操作符，直到遇到左括号。
6. 操作符：

• 如果栈为空或栈顶为左括号，直接压栈。
• 否则，弹出栈中所有优先级高于或等于当前操作符的操作符，然后将当前操作符压栈。

7. 重复上述步骤直到表达式的所有字符被处理完。
8. 将栈中剩余的所有操作符依次弹出并输出到队列。

二、中缀表达式转后缀表达式

以下是一个示例代码，展示如何将中缀表达式转换为后缀表达式：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX 100

typedef struct {
    char data[MAX];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

void push(Stack *s, char c) {
    if (!isFull(s)) {
        s->data[++(s->top)] = c;
    }
}

char pop(Stack *s) {
    if (!isEmpty(s)) {
        return s->data[(s->top)--];
    }
    return '\0';
}

本文原文来自PingCode