Question

蓝桥杯算法训练 java算法 表达式求值

Answer 1

这两天看到的内容是关于栈和队列，在栈的模块发现了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();
Stack ops = new Stack();
Stack vals = new Stack();
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。如果大家还有更好的，更适用的算法，欢迎在评论中给出地址，谢谢。
转载