數(shù)據(jù)結構實驗報告——表達式求值


頁數(shù)：5 字數(shù)：1766


一 實驗內(nèi)容
實現(xiàn)對包含加、減、乘、除和括號這些運算符及浮點型數(shù)據(jù)的表達式的求值。

二 概要設計
本實驗利用棧這種數(shù)據(jù)結構實現(xiàn)表達式求值。棧的核心操作為壓入和彈出元素。
算法的基本思想如下
（1）首先建立一個操作數(shù)棧num和運算符棧opt，將0壓入運算符棧opt作棧底元素，0為最低優(yōu)先級，故根據(jù)（2）中的進棧條件，第一個運算符肯定可入棧。
（2）接收數(shù)字或運算符，若是數(shù)字直接入num棧，若是運算符則與opt棧的棧頂元素比較，若優(yōu)先級高于棧頂元素，入棧，否則棧頂?shù)倪\算符出棧同操作數(shù)棧彈出的兩個操作數(shù)進行運算，然后未入棧的運算符繼續(xù)同opt棧新的棧頂比較，重復以上操作，直到大于時入棧。由這個過程可知，壓入opt棧中上操作符的優(yōu)先級從棧底到棧頂是升序的。
（3）當表達式輸入結束時，對剩余的操作符進行操作，opt棧中上操作符的優(yōu)先級從棧底到棧頂是升序的，則按先出棧的計算就是正確的