游光辉
浙江省萧山中学 311200
摘要：数据结构栈，是一种后进先出的线性数据结构，现实生活中有很多实例具备栈结构。栈结构的学习有栈结构的模型建立、入栈、出栈等操作，在学习时比较抽象。使用项目式教学，让学生在完成项目时，同步学习栈相关的知识。
关键词：数据结构，入栈，出栈
浙江省新一轮课程改革启动后，信息技术学科从技能的学习，转换成培养信息意识、信息社会责任、计算思维以及数字化学习与创新等核心素养，教材内容发生了很大的变化。新的课程中，设置了6门选择性必须课程，包括《数据与数据结构》。该课程在浙江省的高考中，相当于以前的《算法与程序设计》，是选考生重点学习的课程。栈结构处于该课程的第三章，属于线性表中的一种结构，课标要求学生通过问题的解决，理解栈的概念、基本操作，并编程实现。新课程提倡用项目式教学，让学生在完成项目的过程中，构建知识，探究项目，主动地学习相关内容。
栈结构的学习，分为模型的抽象、模型的建立，以及程序的实现。模型的建立比较抽象，直接以讲授知识点的方法，很枯燥。新课改中建议采用项目式教学方法，用项目贯穿整个章节的学习。项目式学习活动是以学生为中心，让学生在整个项目中承担一定的角色，主动地完成其中的某项任务。在完成任务的过程中，学生会主动地收集信息、获取知识，探究完成项目的各种方法，从而主动的建构知识。以浙教版新教材《数据与数据结构》第三章栈结构的“口算批改”项目为例，让学生承担团队任务中的表达式计算的角色。学生从小学阶段开始，就开始学习过加减乘除等数学运算，对数学表达式的计算非常熟悉，计算步骤了然于胸，适合此角色。
该项目实施的过程，分为准备数据、抽象与建模、设计算法、编写程序与测试等。
1.准备数据。数据的采集过程中，可以利用一些识别软件，识别小学口算训练中的一些做过的算式，得到一些等式，方便后面的计算的验证。
2.抽象与建模。不给计算机设定任何的指令时，它并不具备人脑功能。需要按照以下过程进行抽象与建模。
（1）如何提取出计算式中的数字和运算符号？口算训练中的那些等式，相当于一串字符，需要把等式中的数字和运算符号提出来，再进行相应的计算。比如计算式：
（31-11）/2*3
读入时，以整串读入，存入字符串S中，再从S串中分离出数字与运算符号。从上述例子观察到，数字既有单位数，也有多位数的情况，需要循环提取数字。对于运算符号，加减乘除括号等，都是单个字符，可以逐个提取。
（2）如何体现加、减、乘、除、括号等运算符号的优先级？
结合数学中的计算规律，加法与减法运算设置为同一级别，乘法与除法设置为同一级别，括号级别最高。从左往右扫描时，遇到运算符号时，按上述优先级别进行设计算法。
（3）结合运算符号的优先级，程序中如何设计数字与运算符号的计算？
栈结构具备后进先出的特性，结合运算规律，可以建一个符号栈和一个数字栈。数字栈用来存储数字，符号栈存储运算符号。从左往右扫描，遇到数字时，直接压入栈；遇到符号时，判断符号栈顶的运算符号：
①遇到“(”，直接入符号栈；
②遇到加减乘除等运算符号时，当优先性大于栈顶的运算符号时，则压入符号栈；否则栈顶运算符号依次出栈，并从数字栈中取出栈顶的两个数字，用刚刚弹出栈顶的运算符号进行运算，并把结果再压入数字栈。反复操作，直至大于栈顶运算符号的优先性。再把该运算符号压入符号栈。
③遇到“)”时，将运算符号栈中的运算符号依次出栈，每次出栈时，都从数字栈中取出处于栈中顶端的两个数字，并用刚才的运算符号进行运算。重复操作，直至遇到“)”，并把“)”弹出栈。
3.设计算法
建立一个数字栈num和一个运算符号栈st。num负责存储每次扫描到的数字，以及每次计算得到的中间结果，st负责存储运算符号，对于上述例子，双栈过程如下：
①遇到左括号“(”，入符号栈st;遇到数字3，有可能是多位数，要继续扫，得到31，入数字栈num。
②遇到减号“-”，入符号栈st；遇到数字1，继续扫，得到11，入数字栈num。
③遇到右括号“)”，从符号栈st栈顶开始，往下找，直至左括号。期间遇到的所有运算符号都出栈。此时栈顶元素为“-”号，出栈，同时连续取出数字栈num的栈顶元素11和栈顶下面的那个元素31，操作为：31-11=21。此时数字栈num为空栈，再把运算结果21压入栈num。同时弹出st栈的“-”号。此时st栈遇到左括号“(”，再弹出左括号。
④继续扫描，遇到“/”号，直接入符号栈st；遇到数字2，入数字栈num。
⑤继续扫描，遇到“*”号，与st栈顶元素“/”比较。它的优先级别不大于“/”号，则“/”出栈，同时数字栈的2，20依次栈，进行计算，得到结果10。把10压入数字栈num，同时把“*”压入符号栈st。
⑥继续扫描，数字3入数字栈num。最后把st栈中的“*”出栈，再把数字栈中的3,10出栈：10*3=30。得到最终结果。
6个步骤的入栈、出栈过程如下图所示。
.png)
4.编写程序与测试。
根据模型，以及设计的算法，用Python实现。程序中字符串a表示输入的表达式，top1表示数字栈指针，top2表示符号栈指针。部分程序实现如下：
.png)
在项目的实施过程中，学生作为设计“数学表达式”计算的算法模型及编写程序的角色，主动地查找资料，寻找设计算法模型的方法，抽象与建模，设计出数字栈和符号栈，并用python编码程序，完成“数学表达式”的计算。