棧在表達(dá)式求值中的應(yīng)用

李橙+丁國棟

摘要：棧是限定只能在表的一端進(jìn)行插入和刪除的線性表。根據(jù)棧的這種存取特征，棧也被稱為后進(jìn)先出表。生活中的穿衣脫衣、九連環(huán)游戲、括號(hào)匹配等都是應(yīng)用棧的這一特點(diǎn)。棧的基本操作包括入棧、出棧、得到棧頂元素、判斷?？铡⑴袛鄺M等等。在該文中我們將討論棧在中綴表達(dá)式求值、后綴表達(dá)式求值以及后綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式中的應(yīng)用。

關(guān)鍵詞：棧；數(shù)據(jù)結(jié)構(gòu)；線性表；表達(dá)式求值

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8156-02

1 問題描述與分析

中綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算數(shù)之間的表達(dá)式，其中包含運(yùn)算數(shù)、+、-、*、/等各種運(yùn)算符以及括號(hào)。eg.3+9*（1-4）。按照“運(yùn)算符的優(yōu)先級(jí)”求值。

后綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算數(shù)之后的表達(dá)式，其中包含運(yùn)算數(shù)、+、-、*、/等各種運(yùn)算符但不包含括號(hào)，按照順序計(jì)算法求值。

[中綴表達(dá)式＼&后綴表達(dá)式＼&A+B*C＼&ABC*+＼&B*（D-C）+A＼&BDC-*A+＼&]

2 核心算法思想

2.1中綴表達(dá)式求值的算法思想

需要建立兩個(gè)輔助數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)棧用來存放要計(jì)算的數(shù)據(jù)以及產(chǎn)生的結(jié)果；符號(hào)棧用來存放運(yùn)算符。

分析：先乘除，后加減，從左到右。

2.2 后綴表達(dá)式求值的算法思想

需要建立一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)棧用來存放運(yùn)算的數(shù)據(jù)以及產(chǎn)生的結(jié)果。

算法：自左向右掃描后綴表達(dá)式，直到遇到結(jié)束符為止。遇到運(yùn)算數(shù)就進(jìn)棧，遇到運(yùn)算符就從數(shù)棧中退出兩個(gè)運(yùn)算數(shù)，進(jìn)行運(yùn)算，將運(yùn)算結(jié)果進(jìn)棧，一直到所有運(yùn)算全部執(zhí)行完。

2.3 中綴表達(dá)式Mid[]轉(zhuǎn)換為后綴表達(dá)式Post[]

3 算法中涉及到的輔助數(shù)據(jù)結(jié)構(gòu)

4 跟蹤實(shí)例

4.1中綴表達(dá)式求值：Mid=”3*（7-2）#”

4.2 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式

5 算法具體實(shí)現(xiàn)

5.1中綴表達(dá)式求值算法

5.2后綴表達(dá)式求值算法

5.3后綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式的算法

6 結(jié)束語

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)中非常重要的一門專業(yè)基礎(chǔ)課，但很多同學(xué)反映數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)存在各種各樣的難點(diǎn)，其中比較復(fù)雜的是數(shù)據(jù)結(jié)構(gòu)中存在各種各樣的存儲(chǔ)結(jié)構(gòu)，它們有著不同的邏輯結(jié)構(gòu)、不同的存儲(chǔ)結(jié)構(gòu)、不同的運(yùn)算操作以及不同的應(yīng)用。另外和C語言中不同，數(shù)據(jù)結(jié)構(gòu)中的程序由于要定義各種結(jié)構(gòu)，分配各種存儲(chǔ)空間，定義各種初始化操作，數(shù)據(jù)結(jié)構(gòu)中的程序都比較復(fù)雜也比較長，所以在數(shù)據(jù)結(jié)構(gòu)課程中編寫程序要比在C語言中編寫程序復(fù)雜得多。如果我們能夠在各種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上拓展其有趣的應(yīng)用，我們就能激發(fā)學(xué)生的學(xué)習(xí)和編程興趣。

參考文獻(xiàn)：

[1] 譚浩強(qiáng).C語言程序設(shè)計(jì)教程[M].北京：高等教育出版社，1991.

[2] 李志剛.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘的原理及應(yīng)用[M]. 北京：高等教育出版社，2008.

[3] 張俊妮.數(shù)據(jù)挖掘與應(yīng)用[M]. 北京：北京大學(xué)出版社，2009.

[4] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2007.

[5] 李廉治，姜文清，郭福順.數(shù)據(jù)結(jié)構(gòu)[M].大連：大連理工大學(xué)出版社，1989.

[6] 陳文偉.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘教程[M]. 北京：清華大學(xué)出版社，2009.

[7] 馬靖善.C語言程序設(shè)計(jì)[M]. 北京：清華大學(xué)出版社，2005.

[8] 韓家煒.數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京：機(jī)械工業(yè)出版社，2007.

[9] 晉良潁.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：人民郵電出版社，2002.

[10] 許卓群，唐世渭.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：高等教育出版社，1988.

[11] 魏榮.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：機(jī)械工業(yè)出版社，1996.endprint

摘要：棧是限定只能在表的一端進(jìn)行插入和刪除的線性表。根據(jù)棧的這種存取特征，棧也被稱為后進(jìn)先出表。生活中的穿衣脫衣、九連環(huán)游戲、括號(hào)匹配等都是應(yīng)用棧的這一特點(diǎn)。棧的基本操作包括入棧、出棧、得到棧頂元素、判斷?？?、判斷棧滿等等。在該文中我們將討論棧在中綴表達(dá)式求值、后綴表達(dá)式求值以及后綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式中的應(yīng)用。

關(guān)鍵詞：棧；數(shù)據(jù)結(jié)構(gòu)；線性表；表達(dá)式求值

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8156-02

1 問題描述與分析

中綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算數(shù)之間的表達(dá)式，其中包含運(yùn)算數(shù)、+、-、*、/等各種運(yùn)算符以及括號(hào)。eg.3+9*（1-4）。按照“運(yùn)算符的優(yōu)先級(jí)”求值。

后綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算數(shù)之后的表達(dá)式，其中包含運(yùn)算數(shù)、+、-、*、/等各種運(yùn)算符但不包含括號(hào)，按照順序計(jì)算法求值。

[中綴表達(dá)式＼&后綴表達(dá)式＼&A+B*C＼&ABC*+＼&B*（D-C）+A＼&BDC-*A+＼&]

2 核心算法思想

2.1中綴表達(dá)式求值的算法思想

需要建立兩個(gè)輔助數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)棧用來存放要計(jì)算的數(shù)據(jù)以及產(chǎn)生的結(jié)果；符號(hào)棧用來存放運(yùn)算符。

分析：先乘除，后加減，從左到右。

2.2 后綴表達(dá)式求值的算法思想

需要建立一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)棧用來存放運(yùn)算的數(shù)據(jù)以及產(chǎn)生的結(jié)果。

算法：自左向右掃描后綴表達(dá)式，直到遇到結(jié)束符為止。遇到運(yùn)算數(shù)就進(jìn)棧，遇到運(yùn)算符就從數(shù)棧中退出兩個(gè)運(yùn)算數(shù)，進(jìn)行運(yùn)算，將運(yùn)算結(jié)果進(jìn)棧，一直到所有運(yùn)算全部執(zhí)行完。

2.3 中綴表達(dá)式Mid[]轉(zhuǎn)換為后綴表達(dá)式Post[]

3 算法中涉及到的輔助數(shù)據(jù)結(jié)構(gòu)

4 跟蹤實(shí)例

4.1中綴表達(dá)式求值：Mid=”3*（7-2）#”

4.2 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式

5 算法具體實(shí)現(xiàn)

5.1中綴表達(dá)式求值算法

5.2后綴表達(dá)式求值算法

5.3后綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式的算法

6 結(jié)束語

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)中非常重要的一門專業(yè)基礎(chǔ)課，但很多同學(xué)反映數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)存在各種各樣的難點(diǎn)，其中比較復(fù)雜的是數(shù)據(jù)結(jié)構(gòu)中存在各種各樣的存儲(chǔ)結(jié)構(gòu)，它們有著不同的邏輯結(jié)構(gòu)、不同的存儲(chǔ)結(jié)構(gòu)、不同的運(yùn)算操作以及不同的應(yīng)用。另外和C語言中不同，數(shù)據(jù)結(jié)構(gòu)中的程序由于要定義各種結(jié)構(gòu)，分配各種存儲(chǔ)空間，定義各種初始化操作，數(shù)據(jù)結(jié)構(gòu)中的程序都比較復(fù)雜也比較長，所以在數(shù)據(jù)結(jié)構(gòu)課程中編寫程序要比在C語言中編寫程序復(fù)雜得多。如果我們能夠在各種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上拓展其有趣的應(yīng)用，我們就能激發(fā)學(xué)生的學(xué)習(xí)和編程興趣。

參考文獻(xiàn)：

[1] 譚浩強(qiáng).C語言程序設(shè)計(jì)教程[M].北京：高等教育出版社，1991.

[2] 李志剛.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘的原理及應(yīng)用[M]. 北京：高等教育出版社，2008.

[3] 張俊妮.數(shù)據(jù)挖掘與應(yīng)用[M]. 北京：北京大學(xué)出版社，2009.

[4] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2007.

[5] 李廉治，姜文清，郭福順.數(shù)據(jù)結(jié)構(gòu)[M].大連：大連理工大學(xué)出版社，1989.

[6] 陳文偉.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘教程[M]. 北京：清華大學(xué)出版社，2009.

[7] 馬靖善.C語言程序設(shè)計(jì)[M]. 北京：清華大學(xué)出版社，2005.

[8] 韓家煒.數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京：機(jī)械工業(yè)出版社，2007.

[9] 晉良潁.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：人民郵電出版社，2002.

[10] 許卓群，唐世渭.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：高等教育出版社，1988.

[11] 魏榮.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：機(jī)械工業(yè)出版社，1996.endprint

摘要：棧是限定只能在表的一端進(jìn)行插入和刪除的線性表。根據(jù)棧的這種存取特征，棧也被稱為后進(jìn)先出表。生活中的穿衣脫衣、九連環(huán)游戲、括號(hào)匹配等都是應(yīng)用棧的這一特點(diǎn)。棧的基本操作包括入棧、出棧、得到棧頂元素、判斷棧空、判斷棧滿等等。在該文中我們將討論棧在中綴表達(dá)式求值、后綴表達(dá)式求值以及后綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式中的應(yīng)用。

關(guān)鍵詞：棧；數(shù)據(jù)結(jié)構(gòu)；線性表；表達(dá)式求值

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8156-02

1 問題描述與分析

中綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算數(shù)之間的表達(dá)式，其中包含運(yùn)算數(shù)、+、-、*、/等各種運(yùn)算符以及括號(hào)。eg.3+9*（1-4）。按照“運(yùn)算符的優(yōu)先級(jí)”求值。

后綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算數(shù)之后的表達(dá)式，其中包含運(yùn)算數(shù)、+、-、*、/等各種運(yùn)算符但不包含括號(hào)，按照順序計(jì)算法求值。

[中綴表達(dá)式＼&后綴表達(dá)式＼&A+B*C＼&ABC*+＼&B*（D-C）+A＼&BDC-*A+＼&]

2 核心算法思想

2.1中綴表達(dá)式求值的算法思想

需要建立兩個(gè)輔助數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)棧用來存放要計(jì)算的數(shù)據(jù)以及產(chǎn)生的結(jié)果；符號(hào)棧用來存放運(yùn)算符。

分析：先乘除，后加減，從左到右。

2.2 后綴表達(dá)式求值的算法思想

需要建立一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)棧用來存放運(yùn)算的數(shù)據(jù)以及產(chǎn)生的結(jié)果。

算法：自左向右掃描后綴表達(dá)式，直到遇到結(jié)束符為止。遇到運(yùn)算數(shù)就進(jìn)棧，遇到運(yùn)算符就從數(shù)棧中退出兩個(gè)運(yùn)算數(shù)，進(jìn)行運(yùn)算，將運(yùn)算結(jié)果進(jìn)棧，一直到所有運(yùn)算全部執(zhí)行完。

2.3 中綴表達(dá)式Mid[]轉(zhuǎn)換為后綴表達(dá)式Post[]

3 算法中涉及到的輔助數(shù)據(jù)結(jié)構(gòu)

4 跟蹤實(shí)例

4.1中綴表達(dá)式求值：Mid=”3*（7-2）#”

4.2 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式

5 算法具體實(shí)現(xiàn)

5.1中綴表達(dá)式求值算法

5.2后綴表達(dá)式求值算法

5.3后綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式的算法

6 結(jié)束語

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)中非常重要的一門專業(yè)基礎(chǔ)課，但很多同學(xué)反映數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)存在各種各樣的難點(diǎn)，其中比較復(fù)雜的是數(shù)據(jù)結(jié)構(gòu)中存在各種各樣的存儲(chǔ)結(jié)構(gòu)，它們有著不同的邏輯結(jié)構(gòu)、不同的存儲(chǔ)結(jié)構(gòu)、不同的運(yùn)算操作以及不同的應(yīng)用。另外和C語言中不同，數(shù)據(jù)結(jié)構(gòu)中的程序由于要定義各種結(jié)構(gòu)，分配各種存儲(chǔ)空間，定義各種初始化操作，數(shù)據(jù)結(jié)構(gòu)中的程序都比較復(fù)雜也比較長，所以在數(shù)據(jù)結(jié)構(gòu)課程中編寫程序要比在C語言中編寫程序復(fù)雜得多。如果我們能夠在各種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上拓展其有趣的應(yīng)用，我們就能激發(fā)學(xué)生的學(xué)習(xí)和編程興趣。

參考文獻(xiàn)：

[1] 譚浩強(qiáng).C語言程序設(shè)計(jì)教程[M].北京：高等教育出版社，1991.

[2] 李志剛.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘的原理及應(yīng)用[M]. 北京：高等教育出版社，2008.

[3] 張俊妮.數(shù)據(jù)挖掘與應(yīng)用[M]. 北京：北京大學(xué)出版社，2009.

[4] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2007.

[5] 李廉治，姜文清，郭福順.數(shù)據(jù)結(jié)構(gòu)[M].大連：大連理工大學(xué)出版社，1989.

[6] 陳文偉.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘教程[M]. 北京：清華大學(xué)出版社，2009.

[7] 馬靖善.C語言程序設(shè)計(jì)[M]. 北京：清華大學(xué)出版社，2005.

[8] 韓家煒.數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京：機(jī)械工業(yè)出版社，2007.

[9] 晉良潁.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：人民郵電出版社，2002.

[10] 許卓群，唐世渭.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：高等教育出版社，1988.

[11] 魏榮.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：機(jī)械工業(yè)出版社，1996.endprint