栈（2）
前缀、中缀、后缀表达式（逆波兰表达式）
前缀表达式
（1）前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
（2）举例：（3+4）*5-6对应的前缀表达式就是 - * + 3 4 5 6
从右往左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式结果。
例如：（3+4）*5-6对应的前缀表达式就是- * + 3 4 5 6，针对前缀表达式求值步骤如下：
- 从左往右扫描，将6、5、4、3压入堆栈
- 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
- 接下来时*运算符，因此弹出7和5，计算出7 * 5 = 35，将35入栈
- 最后时 - 运算符，计算出35 - 6的值，即29，由此得出最终结果
中缀表达式
（1）中缀表达式就是常见的运算表达式，如（3+4）* 5 - 6
（2）中缀表达式的求值是我们人最熟悉的，但是对计算机来水哦却不好操作（前面我们讲的案例就能看到这个问题），因此，在计算结果时，往往会将中缀表达式转换成其他表达式来操作（一般转为后缀表达式）
因为中缀表达式，需要判断遇到的操作符的优先级和后面遇到的优先级谁高谁低。
后缀表达式
（1）后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后
（2）举例：（3+4）* 5 - 6对应的后缀表达式就是3 4 + 5 * 6 -
（3）再举例：
正常表达式 | 逆波兰表达式 |
|---|---|
a+b | a b + |
a+(b-c) | a b c - + |
a+(b-c)*d | a b c - d * + |
a+d*(b-c) | a d b c - * + |
a=1+3 | a 1 3 + = |
后缀表达式计算机求值，从左往右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如：（3+4）* 5 - 6 对应的前缀表达式就是3 4 + 5 * 6 -，针对后缀表达式求值步骤如下：
（1）从左往右扫描，将3和4压入堆栈；
（2）遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
（3）将5入栈；
（4）接下来是*运算符，因此弹出5和7，计算出7 * 5 = 35，将35入栈；
（5）将6入栈；
（6）最后是 - 运算符，计算出35 - 6的值，即29，由此得出最终结果
接下来我们按照这个理论通过代码实现逆波兰计算器。
逆波兰计算器
需求如下：
（1）输入一个逆波兰表达式，使用（Stack）计算结果
（2）支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
（3）思路分析
（4）完成代码
internal class MyPolandNotaion
{
//先定义一个逆波兰表达式
//（3+4）* 5 - 6对应3 4 + 5 * 6 -
//为了方便，逆波兰表达式的数字和符号使用空格隔开
public static string suffixExpression = "30 4 + 5 * 6 -";
//思路
//1.先将"3 4 + 5 * 6 -"存入一个List中
//2.将AarryList传递一个方法，遍历List配合栈完成计算
//将一个逆波兰表达式，一次将数据和运算符放入到List中
public static List<string> GetListString(string suffixExpression)
{
//将suffixExpression分割
string [] split = suffixExpression.Split(' ');
List<string> list = new List<string>();
foreach (var item in split)
{
list.Add(item);
}
return list;
}
//完成逆波兰表达式的运算
public static int Calculate(List<string> lst)
{
//创建栈，只需要一个栈即可
Stack<string> stack = new Stack<string>();
//遍历list
foreach (var item in lst)
{
//判断是否是数字
if (IsNumber(item))
{
stack.Push(item);
}
else
{
//POP出两个数并运算，再入栈
int num2 = Convert.ToInt32(stack.Pop());
int num1 = Convert.ToInt32(stack.Pop());
int result = 0;
if (item.Equals("+"))
{
result = num1 + num2;
}
else if (item.Equals("-"))
{
result = num1 - num2;
}
else if (item.Equals("*"))
{
result = num1 * num2;
}
else if (item.Equals("/"))
{
result = num1 / num2;
}
else
{
throw new Exception("nothing to do !");
}
stack.Push(result.ToString());
}
}
//最后留在stack中的数据就是计算结果
return Convert.ToInt32(stack.Pop());
}
/// <summary>
/// 判断字符串是否是数字
/// </summary>
public static bool IsNumber(string s)
{
if (string.IsNullOrWhiteSpace(s)) return false;
const string pattern = "^[0-9]*$";
Regex rx = new Regex(pattern);
return rx.IsMatch(s);
}
}
腾讯云开发者
