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

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

原文 http://blog.csdn.net/yujiaxucheng/article/details/79150556

2018-01-25 17:39:25阅读(276)

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

 最终,高手阿毛一语惊醒梦中人,问我是不是想用“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<string, int> dic = new Dictionary<string, int>();
    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<string> strStk = new Stack<string>();                     //栈,用于临时存放运算符和函数名
    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<string> strStk = new Stack<string>();
    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

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹