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());
}
}
}