使用栈进行表达式求值的 C 语言程序

在本文中，您将了解C语言中如何使用栈进行**求值**，以及其不同的方法和示例。

让我们来评估一个**表达式**的字符串表示。您可以假设**括号**匹配正确（如果表达式包含它们）。为了简单起见，假设唯一有效的二元运算是**+、-、***和**/**。算术表达式有三种写法：

1. 中缀表示法

在**中缀表示法**中，运算符写在它们所操作的操作数之间。

例如 5 + 8

**中缀表达式**对计算机来说更难处理，因为确定优先级需要更多时间。**表达式**通常以**中缀表示法**的形式输入到程序中，这也是人类**书写、阅读**和理解表达式的方式。由于它们更难分析，因此通常会转换为以下两种类型之一。

此过程的输出是一个队列，其中包含从输入**中缀表达式**转换而来的**后缀表示法**的表达式。可以使用相同的方法来实现，使其输出表达式的计算结果，而不是**队列**。诀窍在于使用**两个栈**而不是一个，一个用于**运算符**，一个用于**操作数**。

C语言中，**中缀表示法**是编写**数学表达式**的常用方法，将运算符放在操作数之间。这是使用中缀表示法的一个基本数学过程：

示例

输出

Addition of 7 and 8 is: 15
Subtraction of 7 and 8 is: -1
Multiplication of 7 and 8 is: 56
Division of 7 and 8 is: 0

说明

使用**中缀表示法**和**+、-、***和**/运算符**，我们声明两个整数变量**a**和**b**，然后对它们执行多个数学运算。控制台会打印出结果。

2. 前缀表示法

在前缀表示法中，**运算符**写在**操作数**之前。在前缀表示法（也称为**波兰表示法**）中，每个运算符后面都跟着其所有**操作数**。换句话说，运算符位于其**操作数**之前。由于运算符的位置决定了它操作哪些操作数，因此这种表示法消除了对括号的需求，以表示运算顺序。波兰数学家**Jan Ukasiewicz**创建了前缀表示法，它在各种数学和计算机科学情境中使用。

• 运算符位于其**操作数**的前面。
• 运算符的位置明确定义了其**操作数**。因此，在运算顺序方面没有歧义。
• 通常，使用基于栈的技术来分析前缀表达式。
• 例如，考虑中缀表达式**“2 + 3”**。其前缀格式为**“+ 2 3”**。该表达式的分解如下：
• 在操作数**“2”**和**“3”**之前，存在运算符**“+”**，表示加法。
• 要开始计算此表达式，将**“+”运算符**与操作数**“2”**和**“3”**相加，这将得到数字**“5”**。

可以使用以下步骤，在C语言中使用栈数据结构来计算**前缀表达式**：

1. 首先创建一个**空栈**。
2. 应从**左到右**读取表达式。
3. 关于每个操作数或运算符：
4. 如果它是操作数，则将其压入栈。

如果它是**运算符**，则从栈中弹出所需数量的操作数，执行运算，然后将结果推回栈。

在处理完整个表达式后，栈中唯一剩下的将是最终结果。

示例

让我们举一个在C语言中将**中缀转换为前缀**表达式的例子：

输出

The infix is: ((a/b)+c)-(d+(e*f))
The prefix is: -+/abc+d*ef

说明

1. **栈结构：**程序定义了一个名为**stack**的结构来描述栈数据结构。几个转换相关的活动都使用了这个栈。
2. **create function()：**使用**create()函数**来**创建**栈。它为栈的数组分配空间，并将其属性设置为初始值，包括**top、maxSize**以及**数组的内容**。
3. **isFull() 和 isEmpty() 函数：****isFull()**和**isEmpty()**函数都用于确定栈是否**满**或**空**。程序使用这些函数来防止向**满栈**压入元素或从空栈中弹出元素。
4. **push() 函数：**使用**push()函数**向栈中添加元素。
5. **pop() 函数：**使用**pop()函数**可以从栈中删除元素。
6. **peek() 函数：**使用**peek()函数**可以检索栈顶元素而不删除它。
7. **checkIfOperand() 函数：**此函数用于确定一个字符是否为**操作数（变量）**。如果该字符是字母（**大写**或**小写**），表示它是操作数，则返回**true**。
8. **precedence() 函数：**此函数为运算符分配优先级值。**较大的值**表示**较高的优先级**。它返回给定运算符的优先级。
9. **getPostfix() 函数：****getPostfix()函数**将中缀表达式的表示法转换为后缀。由于它在遍历中缀表达式的每个字符时管理栈上的运算符和括号，因此输出是后缀表示法。
10. **reverse() 函数：**此函数反转传递给它的字符串。它用于**临时翻转**中缀表达式，以便于转换为前缀表示法。
11. **brackets() 函数：**此函数将给定字符串中的**'('转换为')'，并将')'转换为')'**。在转换为**后缀表示法**时，此函数处理括号。
12. **InfixtoPrefix() 函数：**将中缀转换为前缀表示法的基本逻辑包含在**InfixtoPrefix()函数**中。它使用**reverse()**函数临时反转**中缀表达式，brackets()**来处理**括号，getPostfix()**来转换为**后缀表示法**，然后将结果反转回前缀表示法，等等。
13. **main() 函数：**程序在main()函数中使用**InfixtoPrefix()函数**执行从**中缀**到**前缀**的转换，该函数还包含一个示例中缀表达式。然后打印出结果前缀表达式。

3. 后缀表示法

**逆波兰表示法（RPN）**，也称为**后缀表示法**，是一种数学表示法，其中每个运算符后面都跟着其所有操作数。换句话说，运算符位于其**操作数**之后。由于运算符的位置决定了它操作哪些操作数，因此这种表示法消除了对括号的需求，以表示运算顺序。波兰数学家**Jan Usiewicz**创建了后缀表示法，如今在计算机科学和计算器中被广泛使用。

后缀表达式

• 运算符位于其操作数之后。
• 由于运算符的位置明确地标识了其操作数，因此在运算顺序方面没有误解。
• 通常，使用**基于栈**的技术来计算**后缀表达式**。
• 例如，考虑中缀表达式**“2 + 3”**。在后缀表示法中，它表示为**“2 3 +”**。对该表达式的解释如下：
• 操作数**“2”**和**“3”**位于运算符**“+”**之前。
• 要计算此表达式，您将首先将**“+”**运算符与操作数**“2”**和**“3”**相加，这将得到数字**“5”**。

使用栈数据结构和以下通用技术，您可以在C语言中计算后缀表达式。

1. 创建一个**新栈**。
2. 从**左到右**读取**表达式**。
3. 每个元素是运算符还是操作数：
4. 如果是操作数，则将其压入栈的**顶部**。
5. 如果是运算符，则从栈中弹出所需数量的操作数，执行运算，然后将结果推回栈。
6. 一旦处理完整个表达式，栈中唯一剩下的将是**最终结果**。

示例

让我们举一个在C语言中将**中缀转换为后缀**表达式的例子：

输出

ASSUMPTION: The infix expression contains single-letter variables and single-digit constants only.
Enter Infix expression: 3+4-2*1/8
Postfix Expression: 34+21*8/-

说明

1. **栈数据结构：**程序利用基于数组的栈在**转换过程**中临时存储运算符。**全局数组**stack用于实现**栈**，而一个整数类型的变量**int top**用于跟踪栈顶元素。
2. **push() 函数：**使用**push()函数**将项添加到栈中。在压栈之前，它会检查**栈溢出**。
3. **pop() 函数：**使用**pop()函数**从栈中删除一个项。在返回弹出项之前，它会检查**栈下溢**。
4. **is_operator() 函数：****is_operator()函数**检查给定的字符是否为运算符**（、*、/、+、-）**。如果是运算符，则返回**1**；否则返回**0**。
5. **precedence() 函数：**此函数为运算符分配优先级值。**较大的值**表示**较高的优先级**。它返回给定运算符的优先级。
6. **InfixToPostfix() 函数：**程序的核心组件是**InfixToPostfix()函数**。它将中缀表达式转换为**后缀表达式**。操作包括：
   • 在**中缀表达式**的开头添加'**(**'，在结尾添加'**)**'，以简化处理。
   • 依次遍历**中缀表达式**中的每个字符。
   • 如果它是操作数（数字或字母），则立即将其添加到**后缀表达式**中。
   • 如果它是开括号**“("**，则将其压入栈。
   • 如果它是运算符，则程序会确定其优先级，然后将栈中的运算符添加到**后缀表达式**中，直到找到优先级较低的运算符或开括号**'('**。然后，它会将当前运算符移到栈顶。
   • 如果括号是闭括号**（')'**，则程序会弹出栈中的运算符并将其添加到**后缀表达式**中，直到遇到开括号**（'('）**，然后将其也弹出栈。
   • 它通过确保处理完所有字符后栈为空来检查无效的**中缀表达式**。如果栈为空，则转换成功。否则，它会在指示无效的中缀表达式后退出。
7. **main Function()：**在**main()方法**中，提示用户输入一个**中缀表达式**。然后使用**InfixToPostfix()**将其转换为**后缀表示法**。之后，打印出最终的后缀表达式。