一. 入门
通常我们所看到的算术表达式，运算符总是在两个操作数中间(除)，如(A+B)C，这样的表达式叫做 中缀表达式
这种表达式不同的运算符优先级不同，而且通常含有括号，计算机很难理解这种表达式。在编译系统中，要把人易于理解的表达式翻译成能正确求值的机器指令。编译系统中对中缀形式的算术表达式的处理方式是: 先把中缀表达式转换成后缀表达式，再进行计算。
后缀表达式 就是表达式中的运算符号出现在操作数的后面，并且不含 括号 ，如AB+C。后缀表达式的特点：
- 后缀表达式让操作数和中缀表达式的操作数先后次序相同，只是运算符号的先后次序改变。
- 后缀表达式中没有括号，运算次序就是其执行次序
一个中缀表达式的四则运算规则：
- 1.先乘除后加减
- 2.先括号内在括号外
- 3.同级别先左后右
以A+(B-C/D)E 为例，它的后缀表达式为：
ABCD/-E+
其运算次序为：T1=CD/;T2 = BT1-;T3 =T2E*;T4=AT3+;
基于后缀表达式的两个特点，计算过程如下:计算时只要从左到右依次扫描后缀表达式的各个单词，当读到的单词为运算符时，就运算的该运算符前两个操作数，然后讲结果T插入到后缀表达式重复上面的操作。
补充知识
栈（Stack） 想象成一个箱子，后来的放在最上面，先进后出；
队列（Queue）想象成一条路，一个入口一个出口，先进先出；
栈和队列是两种受限的线性表。
（线性表：一种线性结构，含有N>=0个节点的有限序列，同一个线性表中的数据元素数据类型相同并且满足一对一的逻辑关系。）
（受限表现在，栈的插入和删除操作只允许在表的尾端进行，即栈顶，满足First In Last Out；
队列只允许在表尾插入数据元素，在表头删除数据元素，满足First In First Out）
二.中缀表达式转后缀表达式
1. 规则
中缀表达式 a+b * c + ( d * e + f ) * g ，其转换成后缀表达式为 a b c * + d e * f + g * +
具体过程如下：
1） 遇到操作数，直接输出
2） 遇到操作符，则放到栈中，遇到左括号也放入栈中
3） 遇到右括号，则将栈元素弹出，将弹出的操作符输出到左括号位置，注意，括号只弹出不输出
4） 遇到操作符的优先级低于或等于栈顶操作符，则弹出直至为空或发现比遇到的操作符更低优先级的，括号的优先级是最高的
5） 当读到末尾，则将栈中所有的元素依次弹出
6） 理解栈的优先级，栈顶最高，依次下降
2.代码
public static string midToRPN(string tmp)
{
var sRet = "";//后缀表达式
var stringArr = SplitFunc(tmp).Split(new char[] { '\n' }, StringSplitOptions.RemoveEmptyEntries);
var strstk = new Stack<string>();
for (int i = 0; i < stringArr.Length; i++)
{
var item = stringArr[i];
if (!string.IsNullOrEmpty(item))
{
if (!IsOp(item))
{
sRet += item + ",";
}
else
{
if (strstk.Count == 0 || item == "(")
{
strstk.Push(item);
}
else if (item == ")")
{
while (strstk.Peek() != "(")
{
sRet += strstk.Pop() + ",";
}
strstk.Pop();//( 出栈
}
else
{
var comRes = comOper(item, strstk.Peek());
if (comRes > 0)
{
strstk.Push(item);
}
else
{
while (strstk.Count > 0 && strstk.Peek() != "(" && comOper(item, strstk.Peek()) <= 0)
{
sRet += strstk.Pop() + ",";
}
strstk.Push(item);
}
}
}
}
}
while (strstk.Count > 0)
{
sRet += strstk.Pop() + ",";
}
return sRet;
}
/// <summary>
/// 借助\n 实现将字符串转换为数组
/// </summary>
/// <param name="tmp"></param>
/// <returns></returns>
public static string SplitFunc(string tmp)
{
if (!string.IsNullOrEmpty(tmp))
{
tmp = tmp.Replace("+", "\n+\n");
tmp = tmp.Replace("-", "\n-\n");
tmp = tmp.Replace("*", "\n*\n");
tmp = tmp.Replace("/", "\n/\n");
tmp = tmp.Replace("(", "\n(\n");
tmp = tmp.Replace(")", "\n)\n");
}
return tmp;
}
/// <summary>
/// 是否为数字，整数
/// </summary>
/// <param name="tmp"></param>
/// <returns></returns>
public static bool IsNumber(string tmp)
{
//int res;
//return int.TryParse(tmp, out res);
return Regex.IsMatch(tmp, @"[0-9]+[.]{0,1}[0-9]*");
}
/// <summary>
/// 判断是否为操作符
/// 简易计算，复杂的还需继续优化
/// </summary>
/// <param name="tmp"></param>
/// <returns></returns>
public static bool IsOp(string tmp)
{
var ops = new string[] { "+", "-", "*", "/", "(", ")" };
return ops.Contains(tmp);
}
/// <summary>
/// 比较操作符
/// </summary>
/// <param name="op1"></param>
/// <param name="op2"></param>
/// <returns>1：大于 -1：小于 0：等于</returns>
public static int comOper(string op1, string op2)
{
var res = 0;
Dictionary<string, int> dic = new Dictionary<string, int>();
dic.Add("+", 1);
dic.Add("-", 1);
dic.Add("*", 2);
dic.Add("/", 2);
dic.Add("(", 100);
dic.Add(")", 100);
if (dic[op1] > dic[op2])
res = 1;
else if (dic[op1] < dic[op2])
res = -1;
return res;
}
三.后缀表达式计算结果
1.规则
循环后缀表达式，遇到数字压入栈中，遇到操作符，从栈中依次取出两个栈顶元素，计算结果后重新压入栈中，直至表达式结束。
2.代码
/// <summary>
/// 借助stack 实现运算
/// </summary>
/// <param name="tmp"></param>
/// <returns></returns>
public static string calRPN(string tmp)
{
var stack = new Stack<string>();
var RPNArr = tmp.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries);
foreach (var item in RPNArr)
{
if (!IsOp(item))
{
stack.Push(item);
}
else
{
stack.Push(CalResult(item, stack.Pop(), stack.Pop()).ToString());
}
}
return stack.Pop();
}
/// <summary>
/// 根据操作符计算结果
/// 注意传入值
/// </summary>
/// <param name="op"></param>
/// <param name="val1"></param>
/// <param name="val2"></param>
/// <returns></returns>
public static double CalResult(string op, string val1, string val2)
{
var res = 0.0;
switch (op)
{
case "+":
res = double.Parse(val2) + double.Parse(val1);
break;
case "-":
res = double.Parse(val2) - double.Parse(val1);
break;
case "*":
res = double.Parse(val2) * double.Parse(val1);
break;
case "/":
if (double.Parse(val1) != 0.0)
res = double.Parse(val2) / double.Parse(val1);
break;
}
return res;
}
网友评论