C＃实现逆波兰表达式并求值

RPN

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

效果如下：

所以，编码工作主要分为以下几块：

一、含有函数的中缀表达式转后缀表达式

1）区分数字、函数名、运算符；

2）将字符串拆分为数组形式，方便入栈；

3）判断运算符、函数的优先级，正确排列顺序【难点】；

二、针对后缀表达式进行计算

1）区分数字、函数名、运算符的不同操作；

2）根据运算规则不同进行入栈、出栈和计算；

梳理计算流程：

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

图二：带有函数名的表达式，中缀转后缀

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

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

具体实现代码：

/*===================================================*/

//RPN and calculate

/*是否为纯数字。正则表达式实现*/

public static bool isNumber(string tmp)

{

return Regex.IsMatch(tmp, @"[0-9]+[.][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

{

}

}

/*==================================================*/