数据结构表达式求值(栈)

数据结构：线性结构—栈实现表达式求值一．问题分析利用栈这种数据结构存储数字和运算符，并实现表达式求值。

为实现按运算符优先顺序进行计算，需要在执行程序的过程中对运算符的优先顺序做出判断。

利用栈先进后出的特点，同时保证优先级最高的运算符始终在栈顶。

当栈顶元素优先级低于读入的运算符时，将该栈顶运算符推出。

这就保证了优先级高的运算符先计算。

二．数据结构—栈1.优先关系表：prior[7][7]={// +-*/()#'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=',' ','>','>','<','>',' ','>','>','<','<','<','<','<',' ','='};将关系表直接用字符型的二维数组存储。

数据结构实验三栈和队列的应用数据结构实验三：栈和队列的应用在计算机科学领域中，数据结构是组织和存储数据的重要方式，而栈和队列作为两种常见的数据结构，具有广泛的应用场景。

本次实验旨在深入探讨栈和队列在实际问题中的应用，加深对它们特性和操作的理解。

一、栈的应用栈是一种“后进先出”（Last In First Out，LIFO）的数据结构。

这意味着最后进入栈的元素将首先被取出。

1、表达式求值在算术表达式的求值过程中，栈发挥着重要作用。

例如，对于表达式“2 ＋ 3 4”，我们可以通过将操作数压入栈，操作符按照优先级进行处理，实现表达式的正确求值。

当遇到数字时，将其压入操作数栈；遇到操作符时，从操作数栈中弹出相应数量的操作数进行计算，将结果压回操作数栈。

最终，操作数栈中的唯一值就是表达式的结果。

2、括号匹配在程序代码中，检查括号是否匹配是常见的任务。

可以使用栈来实现。

遍历输入的字符串，当遇到左括号时，将其压入栈；当遇到右括号时，弹出栈顶元素，如果弹出的左括号与当前右括号类型匹配，则继续，否则表示括号不匹配。

3、函数调用和递归在程序执行过程中，函数的调用和递归都依赖于栈。

当调用一个函数时，当前的执行环境（包括局部变量、返回地址等）被压入栈中。

当函数返回时，从栈中弹出之前保存的环境，继续之前的执行。

递归函数的执行也是通过栈来实现的，每次递归调用都会在栈中保存当前的状态，直到递归结束，依次从栈中恢复状态。

二、队列的应用队列是一种“先进先出”（First In First Out，FIFO）的数据结构。

1、排队系统在现实生活中的各种排队场景，如银行排队、餐厅叫号等，可以用队列来模拟。

新到达的顾客加入队列尾部，服务完成的顾客从队列头部离开。

通过这种方式，保证了先来的顾客先得到服务，体现了公平性。

2、广度优先搜索在图的遍历算法中，广度优先搜索（BreadthFirst Search，BFS）常使用队列。

从起始节点开始，将其放入队列。

/**************************************************************************** 2、算术表达式求值(必做) （栈）时间：2012年12月[问题描述]一个算术表达式是由操作数( operand)、运算符(operator )和界限符(delimiter)组成的。

假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“# ”，如：#（7+15）*（23-28/4）#。

引入表达式起始、结束符是为了方便。

编程利用“算符优先法”求算术表达式的值。

[基本要求]（1）从键盘或文件读入一个合法的算术表达式，输出正确的结果。

（2）显示输入序列和栈的变化过程。

（3）考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。

***************************************************************************/ #include <stdio.h>#include <stdlib.h>#include <string.h>#define OVERFLOW 0#define ERROR 0#define OK 1#define STACK_INIT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量#define MAXSIZE 100#define N 100//*********************************************************************** struct expression{double result;char expstr[MAXSIZE];}exp;typedef struct{char *base; //在栈构造之前和销毁之后,base的值为NULLchar *top; //操作符栈栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位}StackOPTR;//操作符栈typedef struct{float *base; //在栈构造之前和销毁之后,base的值为NULLfloat *top; //操作数栈栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位}StackOPND;//操作数栈//************************栈的基本操作************************************************//***初始化***void InitStack(StackOPTR &S)//操作符栈初始化{S.base=(char *)malloc(STACK_INIT_SIZE * sizeof(char));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}void InitStack(StackOPND &S)//操作数栈初始化{S.base=(float *)malloc(STACK_INIT_SIZE * sizeof(float));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}//***GetTop***int GetTop(StackOPTR S,char &e)//若操作符栈不空，则用e返回s的栈顶元素{if(S.top==S.base)return ERROR;e=*(S.top-1);return OK;}int GetTop(StackOPND S,float &e)//若操作数栈不空，则用e返回s的栈顶元素{if(S.top==S.base)return ERROR;e=*(S.top-1);return OK;}//***Push***void Push(StackOPTR &S,char e)//插入元素e为新的操作符栈顶元素{if(S.top-S.base>=S.stacksize){S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;}void Push(StackOPND &S,float e)//插入元素e为新的操作数栈顶元素{if(S.top-S.base>=S.stacksize){S.base=(float*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(float));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;}//***Pop***int Pop(StackOPTR &S,char &e)//若操作符栈不空，删除s的栈顶元素,用e返回其值{if(S.top==S.base)return ERROR;e=*--S.top;return OK;}int Pop(StackOPND &S,float &e)//若操作数栈不空，删除s的栈顶元素,用e返回其值{if(S.top==S.base)return ERROR;e=*--S.top;return OK;}#define OPSIZE 7//运算符个数char OP[OPSIZE]={'+','-','*','/','(',')','#'};//运算符集合// 表3.1 算符间的优先关系char Prior[7][7] ={'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=',' ','>','>','>','>',' ','>','>','<','<','<','<','<',' ','='};//***int In(char c,char *OP)//OP是运算符集合，检验是否为运算符{bool check=false;for(int i=0;i<OPSIZE;i++){if(c==OP[i])check=true;}return check;}//***float Operate(float a,char theta,float b)//进行二元运算aeb {switch(theta){case'+':return a+b;break;case'-':return a-b;break;case'*':return a*b;break;case'/':if(b==0){printf("不得出现0作为除数!\n");return 0;}elsereturn a/b;break;default:return 0;}}//***int Xu_Op(char theta,char *OP)//返回运算符c在OP中的序号{int i;for(i=0;i<OPSIZE;i++){if(theta==OP[i])return i;}return 0;}char Precede(char theta1,char theta2)//判断运算符栈的栈顶运算符theta1和读入的运算符theta2优先关系{return Prior[Xu_Op(theta1,OP)][Xu_Op(theta2,OP)];}//****算法健壮性的检查*******int change(char c)//字符都改成编号{switch(c){case'(': return 0;break;case'#': return 1;break;case')': return 2;break;case'+': return 3;break;case'-': return 3;break;case'*': return 4;break;case'/': return 4;break;case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9': return -1;break;default: return -2;}}int Wrong(char *exp)//检查算法的健壮性{char *p,*q;int i=0;//记录括号,i=0,合法。

利用栈来实现算术表达式求值的算法利用栈来实现算术表达式求值的算法算术表达式是指按照一定规则组成的运算式，包含数字、运算符和括号。

在计算机中，求解算术表达式是一项基本的数学运算任务。

根据算术表达式的性质，我们可以考虑利用栈这一数据结构来实现求值算法。

一、算法思路首先，我们需要明确一个重要概念——逆波兰表达式（ReversePolish notation）。

逆波兰表达式是一种没有括号的算术表达式，其运算规则是先计算后面的数字和运算符，再计算前面的数字和运算符。

例如，对于算术表达式“3+4*5-6”，其对应的逆波兰表达式为“3 45 * +6 -”。

那么，我们可以利用栈来实现将中缀表达式转化为逆波兰表达式的过程，具体步骤如下：1. 创建两个栈——操作数栈和操作符栈。

2. 从左到右扫描中缀表达式的每一个数字和运算符，遇到数字则压入操作数栈中，遇到运算符则进行如下操作：（1）如果操作符栈为空或当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符压入操作符栈中。

（2）如果当前运算符的优先级小于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入操作数栈中，重复此过程直到遇到优先级较低的运算符或操作符栈为空为止，然后将当前运算符压入操作符栈中。

3. 扫描完中缀表达式后，若操作符栈不为空，则将其中所有运算符弹出并加入操作数栈中。

4. 最终，操作数栈中存放的就是逆波兰表达式，我们可以按照逆波兰表达式的计算规则来计算其结果。

二、算法优点利用栈来实现算术表达式求值的算法具有以下优点：1. 代码简洁易懂，易于实现和维护。

2. 由于将中缀表达式转化为逆波兰表达式后，可以减少运算符的优先级关系而消除括号，从而减少求值的复杂度，提高程序的执行效率。

三、代码实现下面是利用栈来实现算术表达式求值的算法的Python代码实现：```pythonclass Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[-1]def is_empty(self):return len(self.items) == 0def size(self):return len(self.items)def calculate(op_num1, op_num2, operator):if operator == "+":return op_num1 + op_num2elif operator == "-":return op_num1 - op_num2elif operator == "*":return op_num1 * op_num2elif operator == "/":return op_num1 / op_num2def infix_to_postfix(infix_expr):opstack = Stack()postfix_expr = []prec = {"+": 1, "-": 1, "*": 2, "/": 2, "(": 0} token_list = infix_expr.split()for token in token_list:if token.isdigit():postfix_expr.append(token)elif token == '(':opstack.push(token)elif token == ')':top_token = opstack.pop()while top_token != '(':postfix_expr.append(top_token)top_token = opstack.pop()else:while (not opstack.is_empty()) and(prec[opstack.peek()] >= prec[token]):postfix_expr.append(opstack.pop())opstack.push(token)while not opstack.is_empty():postfix_expr.append(opstack.pop())return " ".join(postfix_expr)def postfix_eval(postfix_expr):opstack = Stack()token_list = postfix_expr.split()for token in token_list:if token.isdigit():opstack.push(int(token))else:op_num2 = opstack.pop()op_num1 = opstack.pop()result = calculate(op_num1, op_num2, token) opstack.push(result)return opstack.pop()infix_expr = "3 + 4 * 5 - 6"postfix_expr = infix_to_postfix(infix_expr)print(postfix_expr)print(postfix_eval(postfix_expr))```四、总结算术表达式求值是一项常见的数学运算任务，利用栈这一数据结构来实现求值算法是一种简单有效的方法，它将中缀表达式转化为逆波兰表达式后，可以消除括号并减少运算符的优先级关系，从而提高程序的执行效率。

栈的应用及特性栈是计算机科学中一种非常重要的数据结构，具有广泛的应用和独特的特性。

下面将详细介绍栈的应用及特性。

一、栈的应用：1. 函数调用：在程序执行过程中，函数的调用和返回通常采用栈进行管理。

当一个函数被调用时，函数的参数和局部变量被压入栈中，函数执行完毕后，这些信息会被弹出栈恢复到调用函数的状态。

2. 表达式求值：在编程语言中，栈可用于表达式求值、中缀表达式转换为后缀表达式等相关操作。

通过利用栈的先进后出特性，可以方便地实现这些功能。

3. 递归算法：递归算法中的递归调用也可以通过栈来实现。

当算法需要递归调用时，将函数和相关变量的信息压入栈中，等到递归结束后，再从栈中弹出恢复状态。

4. 括号匹配：栈也常用于判断表达式中的括号是否匹配。

遍历表达式，遇到左括号时压入栈，遇到右括号时弹出栈顶元素，如果匹配则继续，不匹配则判定为括号不匹配。

5. 浏览器的前进后退：浏览器的前进后退功能可以使用栈实现。

每次浏览一个网页时，将该网页的URL压入栈中，点击后退按钮时，再从栈中弹出上一个URL，即可实现返回上一个网页的功能。

6. 撤销操作：在图形界面软件中，通常会有撤销操作。

使用栈可以将每一步操作的状态依次压入栈中，当用户需要撤销时，再从栈中弹出最近的状态，恢复到之前的操作状态。

二、栈的特性：1. 先进后出：栈是一种后进先出（LIFO）的数据结构，即最新添加的元素最先被访问或者删除。

这一特性使得栈能够方便地实现函数调用和返回等操作。

2. 只能操作栈顶元素：由于栈的特性，只能访问或者修改栈顶元素，无法直接访问或者修改栈中的其他元素。

需要先将栈顶元素弹出后，才能访问或者修改下一个栈顶元素。

3. 顺序存储结构：栈可以使用数组或者链表实现。

使用数组实现时，需要指定栈的最大容量，而使用链表实现时，没有容量限制。

4. 操作复杂度：栈的插入和删除操作只涉及栈顶元素，所以其操作复杂度为O(1)。

但是栈的搜索和访问操作需要从栈顶开始遍历，所以其操作复杂度为O(n)。

栈和队列的应用实例栈和队列都是常用的数据结构，在计算机科学中有着广泛的应用。

以下是一些常见的应用实例：1. 栈的应用实例●表达式求值：使用栈可以方便地对表达式进行求值，如逆波兰表达式求值。

●函数调用：函数调用时，每当进入一个函数，都会将上一个函数的现场信息压入栈中，然后在函数返回时再将其弹出，以便恢复上一个函数的执行现场。

●括号匹配：使用栈可以很方便地检查输入序列中括号的匹配情况。

2. 队列的应用实例●广度优先搜索：在图中进行广度优先搜索时常使用队列，因为它满足“先进先出”的特点，可以确保搜索的顺序是按层次来进行的。

●消息队列：在分布式系统中，消息队列经常用于实现进程之间的通信，以及任务的异步处理。

●缓冲区：在计算机中，经常需要通过使用缓冲区来平衡生产者和消费者之间的速度差异，队列就是一种常用的缓冲区实现方式。

以下是具体的应用实例：栈逆波兰表达式求值逆波兰表达式是一种不需要括号的算术表达式表示方法，它将运算符写在操作数的后面，因此也被称为“后缀表达式”。

例如，中缀表达式“3 + 4 * 2 / (1 - 5)”的逆波兰表达式为“3 4 2 * 1 5 - / +”。

逆波兰表达式求值时，可以使用栈来存储数字和运算符，具体过程如下：1. 遍历逆波兰表达式中的每个元素。

2. 如果当前元素是数字，则压入栈中。

3. 如果当前元素是运算符，则从栈中弹出两个操作数进行运算，并将结果压入栈中。

4. 遍历完逆波兰表达式后，栈顶即为表达式的值。

以下是Python语言实现逆波兰表达式求值的代码：def evalRPN(tokens: List[str]) -> int:stack = []for token in tokens:if token in '+-*/': # 运算符num2 = stack.pop()num1 = stack.pop()if token == '+':stack.append(num1 + num2)elif token == '-':stack.append(num1 - num2)elif token == '*':stack.append(num1 * num2)else:stack.append(int(num1 / num2))else: # 数字stack.append(int(token))return stack[0]该函数接受一个字符串列表tokens，其中包含了逆波兰表达式的所有元素。

表达式求值(数据结构) 表达式求值(数据结构)1.引言1.1 目的1.2 背景1.3 范围2.表达式类型2.1 算术表达式2.1.1 运算符2.1.2 运算数2.2 逻辑表达式2.2.1 逻辑运算符2.2.2 逻辑运算数2.3 字符串表达式2.3.1 字符串连接运算符2.3.2 字符串操作函数3.表达式求值算法3.1 递归下降分析法3.2 栈表达式求值法3.2.1 中缀表达式转后缀表达式3.2.2 后缀表达式求值4.数据结构4.1 操作数栈4.2 运算符栈4.3 后缀表达式栈5.算法实现步骤5.1 输入表达式5.2 初始化栈5.3 处理表达式字符串5.4 根据算法选择相应的方法求值5.5 输出结果6.实例演示6.1 算术表达式求值示例6.2 逻辑表达式求值示例6.3 字符串表达式求值示例7.测试与验证7.1 正常表达式测试7.2 异常表达式测试7.3 性能测试8.总结与展望8.1 本文主要工作8.2 结果评估8.3 存在问题8.4 后续工作附件:附件1、算术表达式求值示例代码附件2、逻辑表达式求值示例代码附件3、字符串表达式求值示例代码法律名词及注释:1.递归下降分析法: 一种基于上下文无关文法进行递归分析的方法，用于处理表达式求值等问题。

2.栈表达式求值法: 使用栈数据结构进行表达式求值的方法。

3.中缀表达式: 常见的数学表达式写法，运算符位于运算数之间。

4.后缀表达式: 也称为逆波兰表达式，运算符位于运算数之后。

5.操作数栈: 用于存储表达式中的操作数的栈。

6.运算符栈: 用于存储表达式中的运算符的栈。

7.后缀表达式栈: 用于存储后缀表达式的栈。

栈是一种常见的数据结构，用于解决许多算法和数据处理问题。

在编程中，栈通常用于处理表达式求值问题。

本篇文章将介绍如何使用栈解决表达式求值问题，并给出对应的C语言代码。

1. 表达式求值问题介绍表达式求值是指计算一个数学表达式的值，通常涉及到四则运算、括号和优先级等概念。

给定一个表达式“3 + 4 * 2”，我们需要得到其计算结果为11。

在编程中，需要将该表达式转换为计算机可识别的形式，并使用算法进行求值。

2. 中缀表达式、前缀表达式和后缀表达式在计算机中常见的表达式有三种形式：中缀表达式、前缀表达式和后缀表达式。

其中，中缀表达式是通常人们在日常生活中使用的表达式形式，如“3 + 4 * 2”。

前缀表达式是运算符位于操作数之前的形式，例如“+ 3 * 4 2”。

后缀表达式则是运算符位于操作数之后的形式，例如“3 4 2 * +”。

3. 使用栈解决表达式求值问题在解决表达式求值问题时，我们可以利用栈的特性来简化计算过程。

具体步骤如下：3.1 将中缀表达式转换为后缀表达式我们需要将中缀表达式转换为后缀表达式，这样可以简化表达式的计算顺序。

具体转换规则如下：- 从左至右扫描中缀表达式的每个数字或符号。

- 如果是操作数，则直接输出。

- 如果是运算符，则弹出栈中所有优先级大于或等于该运算符的运算符，并将其压入栈中，然后压入该运算符。

- 如果是括号，则根据括号的不同情况进行处理。

通过以上规则，我们可以将中缀表达式转换为后缀表达式。

3.2 计算后缀表达式的值得到后缀表达式后，我们可以利用栈来计算其值。

具体步骤如下：- 从左至右扫描后缀表达式的每个数字或符号。

- 如果是操作数，则压入栈中。

- 如果是运算符，则弹出栈中的两个操作数进行相应的运算，并将结果压入栈中。

- 继续扫描直到表达式结束，栈中的值即为所求结果。

通过以上步骤，我们可以使用栈来解决表达式求值问题。

4. C语言代码实现以下是使用C语言实现栈来解决表达式求值问题的代码示例：```c#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct {int top;int capacity;int* array;} Stack;Stack* createStack(int capacity) {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->capacity = capacity;stack->top = -1;stack->array = (int*)malloc(stack->capacity * sizeof(int)); return stack;}int isFull(Stack* stack) {return stack->top == stack->capacity - 1; }int isEmpty(Stack* stack) {return stack->top == -1;}void push(Stack* stack, int item) {if (isFull(stack)) return;stack->array[++stack->top] = item;}int pop(Stack* stack) {if (isEmpty(stack)) return -1;return stack->array[stack->top--];}int evaluatePostfix(char* exp) {Stack* stack = createStack(strlen(exp)); for (int i = 0; exp[i]; i++) {if (isdigit(exp[i])) {push(stack, exp[i] - '0');} else {int val1 = pop(stack);int val2 = pop(stack);switch (exp[i]) {case '+':push(stack, val2 + val1); break;case '-':push(stack, val2 - val1); break;case '*':push(stack, val2 * val1); break;case '/':push(stack, val2 / val1); break;}}}return pop(stack);}int m本人n() {char exp[] = "34*2+";printf("The value of s is d\n", exp, evaluatePostfix(exp));return 0;}```以上代码实现了栈的基本功能，并利用栈来计算后缀表达式的值。

栈的应用：表达式求值的原理一、栈的基本原理1.栈是一种具有特殊操作的线性数据结构。

2.栈的特点是后进先出（LIFO，Last In First Out）的存取方式。

3.栈有两个基本操作：入栈和出栈。

二、表达式求值的概念1.表达式是由运算符和运算对象组成的序列。

2.表达式求值是指根据运算符的优先级和结合性来计算表达式的值。

三、中缀表达式与后缀表达式1.中缀表达式：运算符位于运算对象的中间。

–例如：2 + 32.后缀表达式（逆波兰表达式）：运算符位于运算对象的后面。

–例如：2 3 +四、中缀转后缀表达式1.利用栈实现中缀表达式到后缀表达式的转换。

2.遍历中缀表达式中的每个字符，若为数字，则输出到后缀表达式中；若为运算符，则根据优先级进行处理。

3.将运算符入栈，直到出现低优先级的运算符或左括号。

4.遇到右括号时，将栈中的运算符出栈并输出，直到遇到左括号。

5.将剩余的运算符出栈并输出。

五、后缀表达式求值1.利用栈实现后缀表达式的求值。

2.遍历后缀表达式中的每个字符，若为数字，则入栈；若为运算符，则弹出栈中的两个数字进行计算，并将结果入栈。

3.最后栈中的唯一元素即为表达式的求值结果。

六、示例假设要求解的中缀表达式为：2 + 3 * 4 - 5 1. 将中缀表达式转换为后缀表达式：2 3 4 * + 5 - 2. 根据后缀表达式求值的原则，遍历后缀表达式进行计算： - 遇到数字2，入栈； - 遇到数字3，入栈； - 遇到运算符*，弹出栈中的两个数字3和2进行计算得到6，并将结果入栈； - 遇到运算符+，弹出栈中的两个数字6和4进行计算得到10，并将结果入栈； - 遇到数字5，入栈； - 遇到运算符-，弹出栈中的两个数字10和5进行计算得到5，并将结果入栈。

3. 栈中的唯一元素5即为表达式的求值结果。

七、总结1.栈的应用在表达式求值中起到关键作用。

2.利用栈可以将中缀表达式转换为后缀表达式，并通过对后缀表达式的求值获得最终结果。

数据结构表达式求值在计算机科学中，数据结构是组织和存储数据的方式，而表达式求值则是一个常见且重要的任务。

表达式求值可以帮助我们计算数学表达式的结果，无论是简单的四则运算，还是复杂的包含函数和变量的表达式。

让我们从一个简单的算术表达式开始，比如“2 ＋3 4”。

要计算这个表达式的值，我们不能简单地从左到右依次计算，因为乘法的优先级高于加法。

所以，正确的计算顺序应该是先计算 3 4 ＝ 12，然后再计算 2 ＋ 12 ＝ 14。

为了能够正确地处理表达式中不同运算符的优先级，我们需要使用特定的数据结构和算法。

其中，栈（Stack）是一种非常有用的数据结构。

栈就像是一个只能从一端进出的容器，遵循“后进先出”（Last In First Out，LIFO）的原则。

在表达式求值中，我们可以使用两个栈，一个用来存储操作数（Operand Stack），另一个用来存储运算符（Operator Stack）。

当我们读取表达式中的数字时，将其压入操作数栈；当读取到运算符时，需要和运算符栈顶的运算符比较优先级。

如果当前运算符的优先级高于栈顶运算符，那么将其压入运算符栈；如果当前运算符的优先级低于或等于栈顶运算符，就从操作数栈中弹出相应数量的操作数，进行计算，将结果压回操作数栈，然后再将当前运算符压入运算符栈。

例如，对于表达式“2 ＋3 4”，我们首先读取到数字 2，将其压入操作数栈。

接着读取到“＋”号，此时运算符栈为空，所以将“＋”号压入运算符栈。

然后读取到数字 3，压入操作数栈。

再读取到“”号，由于“”号的优先级高于“＋”号，将“”号压入运算符栈。

接着读取到数字 4，压入操作数栈。

此时，表达式已经读取完毕。

因为“”号的优先级高于“＋”号，所以先从操作数栈中弹出 3 和 4 进行乘法运算，得到 12，将 12 压回操作数栈。

然后从运算符栈中弹出“＋”号，从操作数栈中弹出 2 和 12 进行加法运算，得到 14，这就是表达式的最终结果。