数据结构实验报告.doc

数据结构实验报告——表达式求值


页数：5 字数：1766


一 实验内容
实现对包含加、减、乘、除和括号这些运算符及浮点型数据的表达式的求值。

二 概要设计
本实验利用栈这种数据结构实现表达式求值。栈的核心操作为压入和弹出元素。
算法的基本思想如下
（1）首先建立一个操作数栈num和运算符栈opt，将0压入运算符栈opt作栈底元素，0为最低优先级，故根据（2）中的进栈条件，第一个运算符肯定可入栈。
（2）接收数字或运算符，若是数字直接入num栈，若是运算符则与opt栈的栈顶元素比较，若优先级高于栈顶元素，入栈，否则栈顶的运算符出栈同操作数栈弹出的两个操作数进行运算，然后未入栈的运算符继续同opt栈新的栈顶比较，重复以上操作，直到大于时入栈。由这个过程可知，压入opt栈中上操作符的优先级从栈底到栈顶是升序的。
（3）当表达式输入结束时，对剩余的操作符进行操作，opt栈中上操作符的优先级从栈底到栈顶是升序的，则按先出栈的计算就是正确的