Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Text.RegularExpressions;
- using System.Threading.Tasks;
- namespace ExpressionParser
- {
- public class ExpressionParser
- {
- private static Dictionary<string, int> precedence = new Dictionary<string, int>
- {
- ["("] = -1,
- ["+"] = 2,
- ["-"] = 2,
- ["*"] = 3,
- ["/"] = 3,
- ["^"] = 4,
- };
- public decimal Parse(string expression)
- {
- var tokens = Tokenize(expression);
- var postfixTokens = AsPostfix(tokens);
- return ReducePostfix(postfixTokens);
- }
- private decimal ReducePostfix(string[] postfixTokens)
- {
- var stack = new Stack<decimal>();
- foreach (var token in postfixTokens)
- {
- if (IsNumber(token))
- {
- stack.Push(Decimal.Parse(token));
- }
- else
- {
- var b = stack.Pop();
- var a = stack.Pop();
- stack.Push(Result(token, a, b));
- }
- }
- return stack.Pop();
- }
- private decimal Result(string token, decimal a, decimal b)
- {
- switch (token)
- {
- case "+":
- return a + b;
- case "-":
- return a - b;
- case "/":
- return a / b;
- case "*":
- return a * b;
- case "^":
- return (decimal)Math.Pow((double)a, (double)b);
- default:
- throw new SyntaxException();
- }
- }
- private string[] AsPostfix(string[] tokens)
- {
- var stack = new Stack<string>();
- var outputQueue = new Queue<string>();
- foreach (var token in tokens)
- {
- if(String.IsNullOrWhiteSpace(token))
- {
- //do nothing
- }
- else if (IsNumber(token))
- {
- outputQueue.Enqueue(token);
- }
- else if (IsOperator(token))
- {
- while (stack.Any())
- {
- var tokenOperator = token;
- var stackOperator = stack.Peek();
- if ((IsLeftAssosiative(tokenOperator) && precedence[tokenOperator] == precedence[stackOperator]) ||
- (precedence[tokenOperator] < precedence[stackOperator]))
- {
- outputQueue.Enqueue(stack.Pop());
- }
- else
- {
- break;
- }
- }
- stack.Push(token);
- } else if(token.Equals("("))
- {
- stack.Push(token);
- }
- else if(token.Equals(")"))
- {
- while(stack.Any() && stack.Peek() != "(")
- {
- outputQueue.Enqueue(stack.Pop());
- }
- stack.Pop(); // Pop left parenthesis
- }
- else
- {
- throw new SyntaxException();
- }
- }
- while (stack.Any())
- {
- outputQueue.Enqueue(stack.Pop());
- }
- return outputQueue.ToArray();
- }
- bool IsLeftAssosiative(string token)
- {
- return !token.Equals("^");
- }
- private bool IsOperator(string token)
- {
- return Regex.IsMatch(token, @"[+-/*]{1}");
- }
- private bool IsNumber(string token)
- {
- return Regex.IsMatch(token, @"[0-9]+");
- }
- private string[] specialChars = { "+", "-", "/", "*", "^", "(", ")" };
- private string[] Tokenize(string expression)
- {
- foreach(var specialChar in specialChars)
- {
- expression = expression.Replace(specialChar, " " + specialChar + " ");
- }
- return Regex.Split(expression, @"\s");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement