資料結構實驗
棧的應用——算術表示式求值
張雷2023年4月11日
實驗目的：
1. 掌握棧的特性和基本演算法。
2. 學習利用資料結構解決實際問題的方法。
問題描述：
表示式求值：計算乙個合法的算術表示式（含四則運算、小括號和正的浮點數）的值。若實驗1已完成了多項式的四則運算，則可以改為計算乙個多項式表示式（運算元替換為多項式）的結果，可以只考慮除法能除盡的情況。
實驗內容：
1.子函式解釋：
voidinitstack_f(sqstack_f*s)
voidinitstack_f(sqstack_f*s)
//構造乙個儲存實型（字元型）的空棧，預設空間為100，分配失敗就退出
voidgettop_f(sqstack_f*s,float*e)
voidgettop_c(sqstack_c*s,char*e)
//若棧s不空，則以e帶值返棧頂元素，否則顯示錯誤「error」,並退出程式
voidpush_f(sqstack_f*s,floate)
voidpush_c(sqstack_c*s,chare)
//在s的棧頂插入新的棧頂元素e，若棧的當前空間已滿，則追加儲存空間
voidpop_f(sqstack_f*s,float*e)
voidpop_c(sqstack_c*s,char*e)
//若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程式
2.主要演算法解釋
（一）判斷運算子優先順序的演算法：
算符間的優先關係如下：
（二）中綴表示式轉換為字尾表示式的演算法：
演算法過程描述：
1) 首先將左括號「(」壓進棧，作為棧底元素；
2) 從左而右對算數表示式進行掃瞄，每次讀入乙個字元s1[i]；
3) 若遇到數字或小數點，則立即寫入s2[i]，若遇算數運算子，將「 」（空格）寫入s2[i]；
4) 遇到左括號「(」則壓棧；
5) 若遇算術運算子，如果它們的優先順序比棧頂元素高，則直接進棧，否則彈出棧頂元素輸出到s2[i]，直到新棧頂元素的優先順序比它低，然後將它壓棧；
6) 若遇到右括號「）」，則將棧頂元素輸出到s2[i]，直到棧頂元素為「（」，然後相互抵消；
7) 當掃瞄到「#」符號，表明表示式串已全部輸入，將棧中的運算子全部輸出到s2[i]，並刪除棧頂元素。
（三）表示式求值運算的演算法：
演算法描述：
1） 讀入無括號的字尾表示式；
2） 若為數值和小數點則將其聯合轉換為浮點型後進棧（存放運算元）；
3） 若為運算子，讓棧頂元素和次頂元素與次運算子進行相應的運算，運算結果列印並進棧；
4） 重複2）3）步驟，直到輸入為「#」，則此時棧中的結果便是所追求的表示式的值。
數值轉換為實數的演算法描述：
1） 若為數字，則將其減去'0'的ascii碼後就得到該數的數值，並暫存於乙個變數m上；
2） 若繼續為數字，也將其減去'0'的ascii碼後就得到該數的數值，並將其值加上已存的m*10後的值再存於m；
3） 重複2）步驟直到遇到小數點，從小數點後的數開始，在重複2）步驟的通知，也記下小數點後的位數n；
4） 當遇到「 」（空格）後，即表示此輪需轉換的數已讀入完畢，則將m除以10的你次方，則此時的之記為轉換後的實數。
（四）主程式解釋
int main()
printf("\n\n感謝你的使用！\n\n");
return 0;
}實驗結果：
輸入「1+2*2.5+3*（2+2^2）#」，結果為14，正確；
輸入「3/（2.5+0.5）-1.3#」,結果為 -0.3，正確；
輸入「2+3*2.5-7.2/2#」,結果為 5.9，正確；
……討論總結：
再設計除法運算的演算法時，忘記了除數為0的情況，在助教師兄檢查時發現了這個問題，最後改好了，這說明設計演算法一定要注意細節，最後要感謝助教師兄的熱心幫忙！
附源**：
#include<>
#include<>
#include<>
#define ttack_init_size 100
#define stackincrement 10
typedef structsqstack_f;
typedef struct
sqstack_c;
void initstack_f(sqstack_f *s)
void initstack_c(sqstack_c *s)
void gettop_f(sqstack_f *s,float *e)
*e=*(s->top-1);
}void gettop_c(sqstack_c *s,char *e)
*e=*(s->top-1);
}void push_f(sqstack_f *s,float e)
s->top=s->base+s->stacksize;
s->stacksize+=stackincrement;
} *s->top++=e;
}void push_c(sqstack_c *s,char e)
s->top=s->base+s->stacksize;
s->stacksize+=stackincrement;
} *s->top++=e;
}void pop_f(sqstack_f *s,float *e)
void pop_c(sqstack_c *s,char *e)
int precede(char top_char,char s1_char)
if(pre[0]>=pre[1]) return 1;
else return 0;
}void translate(char *s1)
else switch(s1[i]) {
資料結構算術表示式求值實驗報告
目錄1 前言 1 2 概要設計 1 2.1 資料結構設計 1 2.2 演算法設計 1 2.3 adt描述 2 2.4 功能模組分析 2 3 詳細設計 3 3.1 資料儲存結構設計 3 3.2主要演算法流程圖 或演算法偽 3 4 軟體測試 6 5 心得體會 8 參考文獻 8 附錄 8 在計算機中，算術...
資料結構算術表示式求值課程設計
目錄1 前言 2 2 問題描述 3 3 總體設計 3 3.1 概要設計 3 3.1.1 資料結構的選擇 3 3.1.2 相關功能函式 3 3.1.3 函式模組呼叫關係 4 3.2詳細設計和編碼 5 4 執行與測試 9 4.1 上機除錯 9 4.2 演算法時間和空間效能分析 10 4.3程式執行測試結...
表示式求值
課程設計報告 課程名稱資料結構 課題名稱表示式求值 專業電腦科學與技術 班級0901 學號 200903010102 姓名覃宇星 指導教師李珍輝鄧作傑郭芳 2011年7月7日 湖南工程學院 課程設計任務書 課程名稱 c語言程式設計 課題表示式求值 專業班級計算機0901 學生姓名 學號指導老師周鐵山...