1.介紹
後綴表達式又稱逆波蘭表達式,與前綴表達式相似,只是運算符位於操作數之後
2.舉例說明
(3+4)*5-6對應的後綴表達式就是3 4 +5 * 6 –
3.示例
輸入一個逆波蘭表達式(後綴表達式),使用棧(Stack),計算其結果
思路分析:
從左至右掃描表達式,遇到数字時,將数字壓入堆棧,遇到運算符時,彈出棧頂的兩個數,用運算符對它們做相應的計算(次頂元素 和 棧頂元素),並將結果入棧;
重複上述過程直到表達式最右端,最後運算得出的值即為表達式的結果例如: (3+4)×5-6 對應的後綴表達式就是 3 4 + 5 × 6 – ,
針對後綴表達式求值步驟如下:
從左至右掃描,將3和4壓入堆棧;
遇到+運算符,因此彈出4和3(4為棧頂元素,3為次頂元素),計算出3+4的值,得7,再將7入棧;
將5入棧;
接下來是×運算符,因此彈出5和7,計算出7×5=35,將35入棧;
將6入棧;
最後是-運算符,計算出35-6的值,即29,由此得出最終結果
代碼實現:
using System; using System.Collections.Generic; using System.Text.RegularExpressions; namespace DataStructure { public class PolandNotation { public static void Test() { try { //定義逆波蘭表達式 string suffixExpression = "3 4 + 5 * 6 -"; //將suffixExpression轉換成鏈表的方式 var list = GetListString(suffixExpression); //輸出結果 var result = Calculate(list); Console.WriteLine($"{suffixExpression}的結果是{result}"); } catch (Exception ex) { Console.WriteLine(ex.Message); } } /// <summary> /// 獲取集合 /// </summary> /// <param name="suffixExpression"></param> /// <returns></returns> public static List<string> GetListString(string suffixExpression) { //首先實例化List List<string> list = new List<string>(); //將字符串通過空格切換成數組 string[] split=suffixExpression.Split(" "); //循環添加 foreach (var item in split) { list.Add(item); } return list; } /// <summary> /// 計算 /// </summary> /// <param name="list"></param> /// <returns></returns> public static int Calculate(List<string> list) { //創建棧 Stack<string> stack = new Stack<string>(); //循環遍歷 list.ForEach(item => { //正則表達式判斷是否是数字,匹配的是多位數 if (Regex.IsMatch(item,"\\d+")) { //如果是数字直接入棧 stack.Push(item); } //如果是操作符 else { //出棧兩個数字,並運算,再入棧 int num1 =int.Parse(stack.Pop()); int num2 = int.Parse(stack.Pop()); int result = 0; if(item.Equals("+")) { result = num2 + num1; } else if(item.Equals("*")) { result = num2 * num1; } else if(item.Equals("/")) { result = num2 / num1; } else if (item.Equals("-")) { result = num2 - num1; } else { throw new Exception("無法識別符號"); } stack.Push(""+result); } }); //最後把stack中數據返回 return int.Parse(stack.Pop()); } } }
結果圖:
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※為什麼 USB CONNECTOR 是電子產業重要的元件?
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※台北網頁設計公司全省服務真心推薦
※想知道最厲害的網頁設計公司"嚨底家"!
※新北清潔公司,居家、辦公、裝潢細清專業服務
※推薦評價好的iphone維修中心