1、實驗三 波蘭式和四元式及計算課程 編譯原理 實驗名稱 波蘭式和四元式 第 頁班級 11計本 學號 姓名 實驗日期：2013年 月 日 報告退發 (訂正 、 重做) 一、實驗目的：    將非后綴式用來表示的算術表達式轉換為用逆波蘭式來表示的算術表達式，并計算用逆波蘭式來表示的算術表達式的值。二、實驗說明1、逆波蘭式定義將運算對象寫在前面，而把運算符號寫在后面。用這種表示法表示的表達式也稱做后綴式。逆波蘭式的特點在于運算對象順序不變，運算符號位置反映運算順序。采用逆波蘭式可以很好的表示簡單算術表達式，其優點在于易于計算機處理表達式。2、產生逆波蘭式的前提中綴算術表達式3、逆波

2、蘭式生成的實驗設計思想及算法(1)首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優先級越高的原則。(2)讀入一個用中綴表示的簡單算術表達式，為方便起見,設該簡單算術表達式的右端多加上了優先級最低的特殊符號“#”。(3)從左至右掃描該算術表達式，從第一個字符開始判斷，如果該字符是數字，則分析到該數字串的結束并將該數字串直接輸出。(4)如果不是數字，該字符則是運算符，此時需比較優先關系。做法如下：將該字符與運算符棧頂的運算符的優先關系相比較。如果，該字符優先關系高于此運算符棧頂的運算符，則將該運算符入棧。倘若不是的話，則將此運算符棧頂的運算符從棧中彈出，將該字符入棧。(5)重復上述操作(1)-(

3、2)直至掃描完整個簡單算術表達式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。3、逆波蘭式計算的實驗設計思想及算法(1)構造一個棧，存放運算對象。(2)讀入一個用逆波蘭式表示的簡單算術表達式。(3)自左至右掃描該簡單算術表達式并判斷該字符，如果該字符是運算對象，則將該字符入棧。若是運算符，如果此運算符是二目運算符，則將對棧頂部的兩個運算對象進行該運算，將運算結果入棧，并且將執行該運算的兩個運算對象從棧頂彈出。如果該字符是一目運算符，則對棧頂部的元素實施該運算，將該棧頂部的元素彈出，將運算結果入棧。(4)重復上述操作直至掃描完整個簡單算術表

4、達式的逆波蘭式，確定所有字符都得到正確處理，我們便可以求出該簡單算術表達式的值。三、實驗要求（一）準備： 1.閱讀課本有關章節，2.考慮好設計方案；3.設計出模塊結構、測試數據，初步編制好程序。（二）上課上機： 將源代碼拷貝到機上調試，發現錯誤，再修改完善。第二次上機調試通過。（三）程序要求：程序輸入/輸出示例： 輸出的格式如下：(1)逆波蘭式的生成及計算程序，編制人：姓名，學號，班級(2)輸入一以#結束的中綴表達式(包括+*/（）數字#)：在此位置輸入符號串如4*(28+87*6-75)/8 (3)逆波蘭式為：4&28&87&6*+75-*8/ (4)逆波蘭式test

5、4&28&87&6*+75-*8/=計算結果為237.5備注：(1)在生成的逆波蘭式中如果兩個數相連則用&分隔，如28和87，中間用&分隔；(2)在此位置輸入符號串為用戶自行輸入的符號串注意：1.表達式中允許使用運算符（+-*/）、分割符（括號）、數字，結束符#； 2.如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；3.對學有余力的同學，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以分號分割。同時將預期的輸出結果寫在另一個文本文件中，以便和輸出進行對照；（四）代碼實現using System;using System.Coll

6、ections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Windows.Forms;namespace WindowsFormsApplication1 public partial class Form7 : Form public Form7() InitializeComponent(); private void button4_Click(object sender, Event

7、Args e) if (textBox1.Text = "") MessageBox.Show("請輸入表達式"); else string s = textBox1.Text; int i; for (i = 0; i < s.Length - 1; i+) ; if (si != '#') MessageBox.Show("必須以#結尾"); else string s1, s2; s1 = textBox1.Text; Bolan bol = new Bolan(); s2 = bol.bl(s1); te

8、xtBox2.Text = s2; private class Bolan private string s1, s2="" char ch; char ch1; char ch2; char ex = new char100; Stack<char> stk = new Stack<char>(); public string bl(string s) int i = 0, t = 0; ch = si; i+; while (ch != '#') if (ch >= '0' && ch <

9、;= '9') int sum = 0; while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0' ch = si+; i-; if (s2.Length = 0) s2 +=sum.ToString(); else if(s2s2.Length-1<='9'&&s2s2.Length-1>='0') s2 += "&" + sum.ToString(); el

10、se s2 += sum.ToString(); else if (stk.Count = 0) stk.Push(ch); else switch (ch) case '(': stk.Push(ch); break; case ')': while (stk.Peek() != '(') ch1 = stk.Pop(); ext = ch1; t+; s2 += ch1; stk.Pop(); break; case '+': while (stk.Count != 0 && stk.Peek() != 

11、9;(') ch1 = stk.Pop(); ext = ch1; s2 += ch1; t+; stk.Push(ch); break; case '-': while (stk.Count != 0 && stk.Peek() != '(') ch1 = stk.Pop(); ext = ch1; s2 += ch1; t+; stk.Push(ch); break; case '*': if (stk.Peek() = '*' | stk.Peek() = '/') ch1 = stk.Pop(); ext = ch1; t+; s2 += ch1; stk.Push(ch); break; case '/': if (stk.Peek() = '*' | stk.Peek() = '/') ch1 = stk.Pop(); ext = ch1; t+; s2 += ch1; stk.Push(ch); break; default: break; ch = si; i+; while (stk.Count != 0) ch1 = stk.Pop(); e