C#实现中缀表达式转后缀表达式(RPN)并针对后者进行求值

2018-01-26 10:29:46来源:网络收集作者:程序诗人人点击

分享

[var1]

 最近因工作需要,用到“计算器”功能:输入一串文本,解析后进行计算。这部分只是作为一个简单的应用模块,而不是单独的程序,所以着重在算法的实现上。实际编码前,想过用栈、二叉树、循环递归等各种方法,但都否定掉了。一是因为给别人用的,感觉太复杂讲不清楚,二是我实现起来也有点麻烦。


 最终,高手阿毛一语惊醒梦中人,问我是不是想用“RPN”实现。


 RPN是啥?RPN就是逆波兰表达式,即后缀表达式。正常人类计算公式都是形如:
3+4*2/(5-3)^2+3*(4-2)
COS(900-3*10*30)+123.45+30*30-0.45+TAN(0)
这样的算式,也就是中缀表达式,而比较方便计算机理解的是:
3,4,2,*,5,3,-,2,^,/,+,3,4,2,-,*,+
900,3,10,*,30,*,-,COS,123.45,+,30,30,*,+,0.45,-,0,TAN,+,
这样的后缀表达式(RPN)

效果如下:


C#实现中缀表达式转后缀表达式(RPN)并针对后者进行求值


C#实现中缀表达式转后缀表达式(RPN)并针对后者进行求值


所以,编码工作主要分为以下几块:
一、含有函数的中缀表达式转后缀表达式
    1)区分数字、函数名、运算符;
    2)将字符串拆分为数组形式,方便入栈;
    3)判断运算符、函数的优先级,正确排列顺序;
二、针对后缀表达式进行计算
    1)区分数字、函数名、运算符的不同操作;
    2)根据运算规则不同进行入栈、出栈和计算;
梳理计算流程:

图一:简单算术表达式的中缀转后缀


C#实现中缀表达式转后缀表达式(RPN)并针对后者进行求值


图二:带有函数名的表达式,中缀转后缀


C#实现中缀表达式转后缀表达式(RPN)并针对后者进行求值


图三:简单算术后缀表达式计算


C#实现中缀表达式转后缀表达式(RPN)并针对后者进行求值


图四:带有函数名的后缀表达式计算


C#实现中缀表达式转后缀表达式(RPN)并针对后者进行求值

具体实现代码:
/*===================================*/
//RPN and calculate
/*是否为纯数字。正则表达式实现*/
public static bool isNumber(string tmp)
{
return Regex.IsMatch(tmp, @"[0-9]+[.]{0,1}[0-9]*");
}
/*是否为需拆分的运算符+-*^/() */
public static bool isOp(string tmp)
{
bool bRet = false;
switch (tmp)
{
case "+":
case "-":
case "*":
case "/":
case "^":
case "(":
case ")":
bRet = true;
break;
default:
bRet = false;
break;
}
return bRet;
}
/*是否为一元函数名*/
public static bool isFunc(string tmp)
{
bool bRet = false;
switch (tmp)
{
case "SIN":
case "COS":
case "TAN":
case "SQRT":
bRet = true;
break;
default:
bRet = false;
break;
}
return bRet;
}
/*比较运算符及函数优先级。函数视作运算符进行操作。
返回值:1 表示 大于,-1 表示 小于,0 表示 相等*/
public static int compOper(string op1, string op2)
{
int iRet = 0;
Dictionary dic = new Dictionary();
dic.Add("+", 1);
dic.Add("-", 1);
dic.Add("*", 2);
dic.Add("/", 2);
dic.Add("^", 3);
dic.Add("SIN", 4);
dic.Add("COS", 4);
dic.Add("TAN", 4);
dic.Add("SQRT", 4);
dic.Add("(", 100);
dic.Add(")", 100);
if (dic[op1] > dic[op2])
iRet = 1;
else if (dic[op1] < dic[op2])
iRet = -1;
else
iRet = 0;
return iRet;
}
/*运算符、函数求值*/
public static double calValue(string op, string val1, string val2)
{
double dRet = 0.0d;
switch (op)
{
case "+":
dRet = double.Parse(val1) + double.Parse(val2);
break;
case "-":
dRet = double.Parse(val1) - double.Parse(val2);
break;
case "*":
dRet = double.Parse(val1) * double.Parse(val2);
break;
case "/":
if (double.Parse(val2) != 0)
dRet = double.Parse(val1) / double.Parse(val2);
else
MessageBox.Show("Error!");
break;
case "^":
dRet = Math.Pow(double.Parse(val1), double.Parse(val2));
break;
default:
break;
}
return dRet;
}
public static double calValue(string op, string val1)
{
double dRet = 0.0d;
switch (op)
{
case "SIN":
dRet = Math.Sin(double.Parse(val1));
break;
case "COS":
dRet = Math.Cos(double.Parse(val1));
break;
case "TAN":
dRet = Math.Tan(double.Parse(val1));
break;
case "SQRT":
if (double.Parse(val1) > 0)
dRet = Math.Sqrt(double.Parse(val1));
else
MessageBox.Show("Error!");
break;
default:
break;
}
return dRet;
}
/*按照=+-*^/()分隔出元素*/
public static string splitFunc(string tmp)
{
string sRet = tmp;
sRet = sRet.Replace("=", "/n=/n");
sRet = sRet.Replace("+", "/n+/n");
sRet = sRet.Replace("-", "/n-/n");
sRet = sRet.Replace("*", "/n*/n");
sRet = sRet.Replace("/", "/n//n");
sRet = sRet.Replace("^", "/n^/n");
sRet = sRet.Replace("(", "/n(/n");
sRet = sRet.Replace(")", "/n)/n");
return sRet;
}
/*中缀表达式转后缀表达式
tmp为已经添加分隔符的中缀表达式字符串*/
public static string midToRPN(string tmp)
{
string sRet = ""; //返回值
string[] strArr = splitFunc(tmp.ToUpper()).Split('/n');//字符串数组,存放分隔后的中缀表达式元素
Stack strStk = new Stack(); //栈,用于临时存放运算符和函数名
for (int i = 0; i < strArr.Length; i++)
{
if (string.IsNullOrEmpty(strArr[i])) //分隔后为空的元素剔除
continue;
else if (calString.isNumber(strArr[i])) //纯数字直接入队列
sRet += strArr[i] + ',';
else if (calString.isFunc(strArr[i])) //一元函数名直接入栈
strStk.Push(strArr[i]);
else if (calString.isOp(strArr[i]))//运算符特殊处理
{
if (strStk.Count != 0 && strStk.Peek() == "(" && strArr[i] != ")")//栈不为空,最上层为"(",则运算符直接入栈
{
strStk.Push(strArr[i]);
}
else if (strStk.Count != 0 && strArr[i] == ")")//栈不为空,遇")"则pop至"("为止
{
while (strStk.Peek() != "(")
sRet += strStk.Pop() + ',';
strStk.Pop();
if (strStk.Count != 0 && calString.isFunc(strStk.Peek()))//若"("后为一元函数名,则函数名也pop出
sRet += strStk.Pop() + ',';
}
else if (strStk.Count != 0 && calString.compOper(strArr[i], strStk.Peek()) == -1)
{ //栈不为空,运算符优先级小
while (strStk.Count != 0 && strStk.Peek() != "(" && calString.compOper(strArr[i], strStk.Peek()) == -1)
sRet += strStk.Pop() + ',';//则一直pop【存疑】
if (strStk.Count != 0)//pop至优先级不小于栈顶运算符则交换位置
sRet += strStk.Pop() + ',';//先pop
strStk.Push(strArr[i]); //再push
}
else if (strStk.Count != 0 && calString.compOper(strArr[i], strStk.Peek()) == 0)
{ //运算符优先级相同,先pop再push
sRet += strStk.Pop() + ',';
strStk.Push(strArr[i]);
}
else if (strStk.Count != 0 && calString.compOper(strArr[i], strStk.Peek()) == 1)
{ //运算符优先级大,直接入栈
strStk.Push(strArr[i]);
}
else //其他情况,入栈【存疑】
{
strStk.Push(strArr[i]);
}
}
}
while (strStk.Count > 0)//最后栈内元素全部pop出
{
sRet += strStk.Pop() + ',';
}
return sRet;//返回后缀表达式
}
/*根据传入的后缀表达式,求值
tmp为含,分隔符的后缀表达式 */
public static double calRPN(string tmp)
{
double dRet = 0.0d;
string[] strArr = tmp.Split(',');
Stack strStk = new Stack();
for (int i = 0; i < strArr.Length - 1; i++)
{
if (isNumber(strArr[i]))//纯数字入栈
strStk.Push(strArr[i]);
else if (isOp(strArr[i])) //二元运算符,pop两个元素,计算值后压入栈
strStk.Push(calValue(strStk.Pop(), strStk.Pop(), strArr[i]).ToString());
else if (isFunc(strArr[i]))//一元函数名,pop一个元素,计算后压入栈
strStk.Push(calValue(strArr[i], strStk.Pop()).ToString());
}
dRet = double.Parse(strStk.Pop()); //取最后栈中元素作为结果值
return dRet;
}
/*===================================*/
/*===================================*/
/*调用部分代码*/
private void btnTrans_Click(object sender, EventArgs e)
{
//中缀表达式转后缀表达式
this.tbRPN.Text = calString.midToRPN(this.tbOrigin.Text);
}
private void btnCal_Click(object sender, EventArgs e)
{
//后缀表达式求值
double tmp;
try
{
tmp = calString.calRPN(this.tbRPN.Text);
this.tbRes.Text = tmp.ToString();
}
catch (Exception ex)
{
MessageBox.Show(ex.ToString());
this.tbRes.Text = "Error";
}
finally
{
}
}
/*===================================*/文章地址:https://mp.weixin.qq.com/s/Zdof-uGtQ0CylF544ZYbUA

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台