藉助表達式樹對四則運算表達式進行計算
如何計算像這樣的一個算術表達式:
-5+(-5)+35^3+14*(52+9)
學過數據結構的我們知道, 這是一個中綴表達式, 我們可以先把它轉成前綴或者後綴表達式, 然後計算起來就比較簡單了;
這裡我使用後綴表達式來實現;
預備知識
- 數據結構 – 二叉樹
- 設計模式 – 建造者 策略
- C#中的表達式樹(
Expression)
從後綴表達式生成表達式樹
後綴表達式怎麼生成表達式樹?
我參考了 <<數據結構與演算法分析-C語言描述>> 中給出的一個演算法來實現將後綴表達式轉化成C#中的 Expression:
遍歷後綴表達式字元串數組, 判斷當前是操作符還是操作數, 如果是操作數, 則構造ConstantExpression然後壓棧, 如果是操作符, 則出兩次棧, 構造一個BinaryExpression然後將其壓棧;
這裡使用了建造者模式, 構建表達式樹的函數放在了建造者類裡面, 完整的程式碼地址在文末給出了;
/// <summary>
/// 從後綴表達式生成一個表達式樹
/// </summary>
/// <param name="postFix">後綴表達式</param>
private void BuildExpressionFromPostFix(string[] postFix)
{
var stack = new Stack<Expression>();
BinaryExpression ex;
Expression l, r;
for (int i = 0;i < postFix.Length;i++)
{
if(IsArithmetricOperator(postFix[i]))
{
r = stack.Pop();
l = stack.Pop();
ex = Expression.MakeBinary(
ArthmetricOperatorsMapping[postFix[i][0]],
l, r);
stack.Push(ex);
}
else
{
stack.Push(
Expression.Constant(
double.Parse(postFix[i])));
}
}
if (stack.Peek() is BinaryExpression binaryExpression)
_exprTree = binaryExpression;
else if (stack.Peek() is ConstantExpression constantExpression)
_exprTree = Expression.Add(constantExpression, Expression.Constant(0d)); // 單獨一個表達式 5
}
中綴表達式轉成後綴表達式
這裡輸入的中綴表達式是一個字元串, 輸出一個字元串數組保存後綴表達式
<<數據結構與演算法分析-C語言描述>> 這本書在棧的那一章給出了中綴表達式轉後綴表達式的演算法, 簡單來說就是:
遇到操作數, 操作數放到結果集裡面去;
遇到運算符, 判斷是否要壓棧, 壓棧的條件是
- 如果當前棧空, 則壓棧
- 棧頂的操作符優先順序低於當前操作符的優先順序, 則壓棧
出棧的條件: - 棧頂元素優先順序高於或等於當前操作符的優先順序, 則出棧直到棧頂元素優先順序低於當前操作符, 然後將當前操作符入棧;
具體程式碼, 寫的不好, 歡迎指正, 裡面用到了建造者的成員變數, 完整程式碼看文末鏈接:
/// <summary>
/// 構建後綴表達式
/// </summary>
private void BuildPostFixExpr()
{
if (_postFixExpr == null)
{
var stack = new Stack<char>();
int sIndex = 0;
var list = new List<string>();
// 表達式開頭可能出現 "-" 號
if (_expr.Length > 0 && IsArithmetricOperator(_expr[0]))
_expr = _expr.Insert(0, "0");
for (int i = 0; i< _expr.Length; i++)
{
if (IsArithmetricOperator(_expr[i]))
{
sIndex = i + 1;
if (stack.Count <= 0)
{
stack.Push(_expr[i]);
}
else
{
if (_expr[i] == ')')
{
while (stack.Peek() != '(')
{
list.Add(stack.Pop().ToString());
}
stack.Pop();
}
else if(i+1 < _expr.Length && _expr[i] == '(' &&
_expr[i+1] != '(' && IsArithmetricOperator(_expr[i+1]))
{
_expr = _expr.Insert(i+1, "0"); // 5-(-5) 的情況
stack.Push(_expr[i]);
}
else if (stack.Peek() != '(' && ArithmetricOperatorsPriority[stack.Peek()] >=
ArithmetricOperatorsPriority[_expr[i]])
{
while (stack.Count > 0 && stack.Peek() != '(' && ArithmetricOperatorsPriority[stack.Peek()] >=
ArithmetricOperatorsPriority[_expr[i]])
list.Add(stack.Pop().ToString());
stack.Push(_expr[i]);
}
else
stack.Push(_expr[i]);
}
}
else
{
if ((_expr.Length > i+1 && IsArithmetricOperator(_expr[i+1])) || i == _expr.Length - 1)
list.Add(_expr.Substring(sIndex, i-sIndex+1));
}
}
while (stack.Count > 0)
{
if (stack.Peek() == '(')
{
stack.Pop();
continue;
}
list.Add(stack.Pop().ToString());
}
_postFixExpr = list.ToArray();
}
}
獲得了使用Expression構成的表達式樹, 如何計算最終結果呢
上面我們完成了基於Expression的表達式樹的構建, 需要注意的是, Expression類是一個抽象類, 我們上面的構建的表達式樹主要用到了他的兩個派生類: ConstantExpression和BinaryExpression, 其中BinaryExpression其實就是一個二叉樹節點, 而ConstantExpression呢, 顧名思義,就是一個保存了操作數的常量表達式;
所以最終如何計算得到表達式的結果呢?
有兩種辦法:
這裡的話我使用了策略模式來封裝這兩種方案
策略介面:IExpressionTreeCalculatorEngine
using System.Linq.Expressions;
namespace SimpleCalculator
{
internal interface IExpressionTreeCalculatorEngine
{
double Calculate(Expression expression);
}
}
DefaultCalculatorEngine策略
這個策略比較簡單, 直接將作為參數的傳遞過來的表達式通過 Expression.Lambda() 生成 lambda 表達式然後編譯並調用得到最終結果;
using System;
using System.Linq.Expressions;
namespace SimpleCalculator
{
internal class DefaultCalculatorEngine : IExpressionTreeCalculatorEngine
{
public double Calculate(Expression expression)
{
Func<double> calculate = Expression.Lambda<Func<double>>(expression).Compile();
return calculate();
}
}
}
自己手動後序遍歷遞歸求值(RecursionExpressionTreeCalculatorEngine)
using System;
using System.Diagnostics;
using System.Linq.Expressions;
namespace SimpleCalculator
{
internal sealed class RecursionExpressionTreeCalculatorEngine : ExpressionVisitor,IExpressionTreeCalculatorEngine
{
public double Calculate(Expression expression)
{
Expression exp = Visit(expression);
var constant = exp as ConstantExpression;
return (double)constant.Value;
}
protected override Expression VisitBinary(BinaryExpression node)
{
Expression l = Visit(node.Left);
Expression r = Visit(node.Right);
if (l is ConstantExpression cl && r is ConstantExpression cr)
switch (node.NodeType)
{
case ExpressionType.Add:
Debug.Write($"(+{cl.Value} {cr.Value})");
return Expression.Constant((double)cl.Value+(double)cr.Value);
case ExpressionType.Divide:
Debug.Write($"(/{cl.Value} {cr.Value})");
return Expression.Constant((double)cl.Value/(double)cr.Value);
case ExpressionType.Subtract:
Debug.Write($"(-{cl.Value} {cr.Value})");
return Expression.Constant((double)cl.Value-(double)cr.Value);
case ExpressionType.Multiply:
Debug.Write($"(*{cl.Value} {cr.Value})");
return Expression.Constant((double)cl.Value*(double)cr.Value);
case ExpressionType.PowerAssign:
case ExpressionType.Power:
Debug.Write($"(^{cl.Value} {cr.Value})");
return Expression.Constant(Math.Pow((double)cl.Value, (double)cr.Value));
case ExpressionType.Modulo:
Debug.Write($"(/{cl.Value} {cr.Value})");
return Expression.Constant((double)cl.Value%(double)cr.Value);
//case ExpressionType
default:
throw new NotSupportedException();
}
else
{
Debug.Write(node.ToString());
return node;
}
}
protected override Expression VisitConstant(ConstantExpression node)
{
return node;
}
}
}
這個類通過繼承 ExpressionVisitor 來遞歸遍歷各個表達式節點, 類似二叉樹的後序遍歷;
