數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——表達(dá)式求值


頁數(shù)：5 字?jǐn)?shù)：1766


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

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