Convertion, Evaluation and Build Expression Tree

/**********************************************************************
 * Expression Parser
 * Author: Yin Yang
 * yinyang.it@gmail.com
 * https://yinyangit.wordpress.com
 *
 * Date: 27 Jan 2011
 * Lasted Update: 21 March 2011
 **********************************************************************/

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.Text.RegularExpressions;

namespace Y2_Expression_Converter
{
	public class Y2Expression
	{

		public static string Infix2Prefix(string infix)
		{
			List<string> prefix = new List<string>();
			Stack<string> stack = new Stack<string>();

			infix = FormatExpression(infix);

			IEnumerable<string> enumer = infix.Split(' ').Reverse();// .Where(s => !String.IsNullOrEmpty(s));

			foreach (string s in enumer)
			{
				if (IsOperand(s))
					prefix.Add(s);
				else if (s == ")")
					stack.Push(s);
				else if (s == "(")
				{
					string x = stack.Pop();
					while (x != ")")
					{
						prefix.Add(x);
						x = stack.Pop();
					}
				}
				else// if (IsOperator(s))
				{
					while (stack.Count > 0 && GetPriority(s) < GetPriority(stack.Peek()))
						prefix.Add(stack.Pop());
					stack.Push(s);
				}
			}

			while (stack.Count > 0)
				prefix.Add(stack.Pop());

			StringBuilder str = new StringBuilder();
			for (int i = prefix.Count - 1; i >= 0; i--)
			{
				str.Append(prefix[i]).Append(" ");
			}

			return str.ToString();
		}

		public static string Infix2Postfix(string infix)
		{
			infix = FormatExpression(infix);

			string[] tokens = infix.Split(' ').ToArray();
			Stack<string> stack = new Stack<string>();
			StringBuilder postfix = new StringBuilder();

			for (int i = 0; i < tokens.Length; i++)
			{
				string token = tokens[i];
				if (IsOperator(token))
				{
					if (i > 0 && IsOperator(tokens[i - 1]))
					{
						if (token == "-")
						{
							postfix.Append(token + tokens[i + 1]).Append(" ");
							i++;
						}
						else if (token == "sqrt")
						{
							stack.Push(token);
						}
					}
					else
					{
						while (stack.Count > 0 && GetPriority(token) <= GetPriority(stack.Peek()))
							postfix.Append(stack.Pop()).Append(" ");
						stack.Push(token);
					}
				}

				else if (token == "(")
					stack.Push(token);
				else if (token == ")")
				{
					string x = stack.Pop();
					while (x != "(")
					{
						postfix.Append(x).Append(" ");
						x = stack.Pop();
					}
				}
				else// (IsOperand(s))
				{
					postfix.Append(token).Append(" ");
				}
			}

			while (stack.Count > 0)
				postfix.Append(stack.Pop()).Append(" ");

			return postfix.ToString();
		}

		#region Evaluate

		public static double EvaluatePostfix(string postfix)
		{
			Stack<double> stack = new Stack<double>();
			postfix = postfix.Trim();

			IEnumerable<string> enumer = postfix.Split(' ');

			foreach (string s in enumer)
			{
				if (IsOperator(s))
				{
					double x = stack.Pop();

					if (s == "sqrt")
					{
						x = Math.Sqrt(x);
						stack.Push(x);
					}
					else
					{
						double y = stack.Pop();

						switch (s)
						{
								case "+": y += x; break;
								case "-": y -= x; break;
								case "*": y *= x; break;
								case "/": y /= x; break;
								case "%": y %= x; break;
						}

						stack.Push(y);
					}
				}
				else  // IsOperand
				{
					stack.Push(double.Parse(s));
				}

			}
			return stack.Pop();
		}

		public static double EvaluatePrefix(string prefix)
		{
			Stack<double> stack = new Stack<double>();
			prefix = prefix.Trim();

			IEnumerable<string> enumer = prefix.Split(' ').Reverse();

			foreach (string s in enumer)
			{
				if (IsOperand(s))
					stack.Push(double.Parse(s));
				else
				{
					double y = stack.Pop();
					double x = stack.Pop();

					switch (s)
					{
							case "+": y += x; break;
							case "-": y -= x; break;
							case "*": y *= x; break;
							case "/": y /= x; break;
							case "%": y %= x; break;
					}
					stack.Push(y);
				}
			}
			return stack.Pop();
		}
		public static double EvaluateExpressionTree(BinaryTreeNode node)
		{
			double t = 0;
			if (node.IsLeaf)
				t = double.Parse(node.Value);
			else
			{
				double x = EvaluateExpressionTree(node.LeftChild);
				double y = EvaluateExpressionTree(node.RightChild);

				switch (node.Value)
				{
						case "+": t = x + y; break;
						case "-": t = x - y; break;
						case "*": t = x * y; break;
						case "/": t = x / y; break;
						case "%": t = x % y; break;
				}
			}
			return t;
		}

		#endregion

		#region Create Expression Tree
		/// <summary>
		/// Tạo một cây nhị phân 3 node với node gốc là toán tử, 2 node lá là toán hạng
		/// </summary>
		/// <param name="node"></param>
		/// <param name="opStack"></param>
		/// <param name="nodeStack"></param>
		private static void CreateSubTree(Stack<BinaryTreeNode> opStack, Stack<BinaryTreeNode> nodeStack)
		{
			BinaryTreeNode node = opStack.Pop();
			node.RightChild = nodeStack.Pop();
			if(node.Value!="sqrt")
				node.LeftChild = nodeStack.Pop();
			nodeStack.Push(node);
		}

		public static BinaryTreeNode Infix2ExpressionTree(string infixExpression)
		{
			List<string> prefix = new List<string>();
			Stack<BinaryTreeNode> operatorStack = new Stack<BinaryTreeNode>();
			Stack<BinaryTreeNode> nodeStack = new Stack<BinaryTreeNode>();

			infixExpression = FormatExpression(infixExpression);

			string[] tokens = infixExpression.Split(' ').ToArray();

			for (int i = 0; i < tokens.Count(); i++)
			{
				if (IsOperator(tokens[i]))
				{
					if (i > 0 && IsOperator(tokens[i - 1]))
					{
						if (tokens[i] == "-")
						{
							nodeStack.Push(new BinaryTreeNode(tokens[i] + tokens[i + 1]));
							i++;
						}
						else if(tokens[i]=="sqrt")
							operatorStack.Push(new BinaryTreeNode(tokens[i]));
					}
					else
					{
						while (operatorStack.Count > 0 && GetPriority(operatorStack.Peek().Value) >= GetPriority(tokens[i]))
							CreateSubTree(operatorStack, nodeStack);

						operatorStack.Push(new BinaryTreeNode(tokens[i]));
					}
				}

				else if (tokens[i] == "(")
					operatorStack.Push(new BinaryTreeNode(tokens[i]));
				else if (tokens[i] == ")")
				{
					while (operatorStack.Peek().Value != "(")
						CreateSubTree(operatorStack, nodeStack);
					operatorStack.Pop();
				}
				else //if (IsOperand(tokens[i]))
					nodeStack.Push(new BinaryTreeNode(tokens[i]));
			}

			while (operatorStack.Count > 0)
				CreateSubTree(operatorStack, nodeStack);

			return nodeStack.Peek();
		}

		public static BinaryTreeNode Postfix2ExpressionTree(string postfixExpression)
		{
			Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

			IEnumerable<string> enumer = postfixExpression.Split(' ');

			foreach (string s in enumer)
			{
				BinaryTreeNode node = new BinaryTreeNode(s);
				if (IsOperand(s))
					stack.Push(node);
				else if (IsOperator(s))
				{
					node.RightChild = stack.Pop();
					node.LeftChild = stack.Pop();
					stack.Push(node);
				}
			}
			return stack.Pop();
		}

		#endregion

		#region Common Methods

		public static string FormatExpression(string expression)
		{
			expression = expression.Replace(" ", "");
			expression = Regex.Replace(expression, @"(\+|\-|\*|\/|\%){3,}", match => match.Value[0].ToString());

			expression = Regex.Replace(expression, @"(\+|\-|\*|\/|\%)(\+|\*|\/|\%)", match =>
			                           match.Value[0].ToString()
			                          );
			expression = Regex.Replace(expression, @"\+|\-|\*|\/|\%|\)|\(", match =>
			                           String.Format(" {0} ", match.Value)
			                          );
			expression = expression.Replace("  ", " ");
			expression = expression.Trim();

			return expression;
		}

		public static int GetPriority(string op)
		{
			if (op == "sqrt")
				return 3;
			if (op == "*" || op == "/" || op == "%")
				return 2;
			if (op == "+" || op == "-")
				return 1;
			return 0;
		}

		public static bool IsOperator(string str)
		{
			return Regex.Match(str, @"^(\+|\-|\*|\/|\%|sqrt)$").Success;
		}

		public static bool IsOperand(string str)
		{
			return Regex.Match(str, @"^\d+$|^([a-z]|[A-Z])$").Success;
		}

		#endregion
	}
}

Y2 Expression Converter 1.2_tab2
Bài viết liên quan:

Algorithm – Cải thiện thuật toán chuyển đổi và tính giá trị biểu thức số học

Y2 – Expression Converter Demo (v1.2)- Chuyển biểu thức trung tố sang tiền tố và hậu tố

Algorithm – Tạo và sử dụng cây biểu thức (expression tree)

Algorithm – Tính giá trị của biểu thức tiền tố và hậu tố

Algorithm – Chuyển biểu thức trung tố sang tiền tố và hậu tố bằng Stack

https://yinyangit.wordpress.com

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s