1.介紹
字尾表達式又稱逆波蘭表達式,與字首表達式相似,隻是運算符位于操作數之後
2.舉例說明
(3+4)*5-6對應的字尾表達式就是3 4 +5 * 6 -
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiETPwJWZ3ZCMwcTP39zZuBnLuVzRjVXUq5kMNpmTwcmaOpHMT90dBpmT4VlaNBTRU1UeZRUT3lERNlHMp10dBR1T1kFVNZXWE10dJRUT5hTaNdXQU9UNZRVT2NmMiNnSywEd5ITW110MaZHetlVdO1GT3lERNl3YXJGc5kHT20ESjBjUIF2Lc12bj5SYphXa5VWen5WY35iclN3Ztl2Lc9CX6MHc0RHaiojIsJye.png)
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());
}
}
}