首页 > 代码库 > 算法手记(2)Dijkstra双栈算术表达式求值算法

算法手记(2)Dijkstra双栈算术表达式求值算法

这两天看到的内容是关于栈和队列,在栈的模块发现了Dijkstra双栈算术表达式求值算法,可以用来实现计算器类型的app。

编程语言系统一般都内置了对算术表达式的处理,但是他们是如何在内部实现的呢?为了了解这个过程,我们可以自行搭建一套简易的算术表达式处理机制,这里就用到栈特性和本篇提到的Dijkstra算法。

 

概述:
     算术表达式可能是一个数、或者是由一个左括号、一个算术表达式、一个运算符、另一个算术表达式和一个右括号组成的表达式。为了简化问题,这里定义的是未省略括号的算术表达式,它明确地说明了所有运算符的操作数,形式如下:

                                                                  (1+((2+3)*(4*5)))

 

思路:

     表达式由括号、运算符和操作数构成,我们根据以下4中情况从左至右逐个将这些实体送入栈处理:

     1.将操作数压入操作数栈;

     2.将运算符压入运算符栈;

     3.忽略左括号;

     4.在遇到右括号时,弹出一个运算符,弹出所需数量的操作数,并将运算后的结果压入操作数栈;

    在处理完最后一个右括号时,操作数栈上只会剩下一个值,它就是表达式的计算结果。这种方法咋一看难理解,但要证明它能计算得到正确的值很简单:

    每当算法遇到一个括号包围,并由一个运算符和两个操作数组成的子式时,他都将运算符和操作数运算结果压入操作数栈。这样的结果就像是在输入中用这个值代替了该子表达式,因此用这个值代替子表达式得到的结果和原表达式相同。我们可以反复应用这个规律并得到一个最终值。

例如:

(1+((2+3)*(4*5)))

(1+(5*(4*5)))

(1+(5*20))

(1+100)

  101

 

代码实现:


这里我采用C#来实现,最终运行效果完全符合预期,证明了此算法的正确性,代码如下:

using System;using System.Collections.Generic;using System.Linq;namespace Evaluate{    class Program    {        static void Main(string[] args)        {            string testExpress = "(1+((2+3)*(4*5)))";            Console.WriteLine(Evaluate(testExpress));        }        //DijkStra        static double Evaluate(string express)        {            var expressChars = express.ToArray<char>();            Stack<char> ops = new Stack<char>();            Stack<double> vals = new Stack<double>();            if (express.Length > 0)            {                foreach (var opt in expressChars)                {                    switch (opt)                    {                        case +:                        case -:                        case *:                        case /:                            ops.Push(opt);                            break;                        case ):                            var op = ops.Pop();                            var v = vals.Pop();                            switch (op)                            {                                case +:                                    v += vals.Pop();                                    break;                                case -:                                    v = vals.Pop() - v;                                    break;                                case *:                                    v *= vals.Pop();                                    break;                                case /:                                    v = vals.Pop() / v;                                    break;                            }                            vals.Push(v);                            break;                        case  :                        case (:                            break;                        default:                            vals.Push(double.Parse(opt.ToString()));                            break;                    }                }                return vals.Pop();            }            return double.MaxValue;        }    }}

 

总结:

Dijkstra算法充分利用了栈的特性,具备较高的执行效率,经过进一步的扩充修改,就完全可以实现具备科学计算功能的复杂计算类app。如果大家还有更好的,更适用的算法,欢迎在评论中给出地址,谢谢。

算法手记(2)Dijkstra双栈算术表达式求值算法