Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save bashmohandes/e36e38ebaa866ecd2f939832d6ea60df to your computer and use it in GitHub Desktop.
Save bashmohandes/e36e38ebaa866ecd2f939832d6ea60df to your computer and use it in GitHub Desktop.
using System;
using System.Linq;
using System.Collections.Generic;
class MainClass
{
public static void Main(string[] args)
{
var p = new SimpleParser();
var result = p.RunExpression("");
Console.WriteLine(result);
}
}
// This class is a very simple implementation of Shunting-yard algorithm to parse infix expression to postfix expression, and evaluate it.
class SimpleParser
{
Dictionary<string, int> precendence = new Dictionary<string, int>
{
{"+", 2},
{"-", 2},
{"*", 3},
{"/", 3}
};
public double RunExpression(string input)
{
var opStack = new Stack<string>();
var outputStack = new Stack<string>();
foreach (var token in Tokenize(input))
{
if (precendence.ContainsKey(token))
{
if (opStack.Any())
{
var topOfStack = opStack.Peek();
if (topOfStack != "(" && precendence[topOfStack] >= precendence[token])
{
outputStack.Push(opStack.Pop());
}
}
opStack.Push(token);
}
else if (token == "(")
{
opStack.Push(token);
}
else if (token == ")")
{
while (opStack.Peek() != "(")
{
outputStack.Push(opStack.Pop());
}
if (opStack.Any())
{
opStack.Pop();
}
}
else
{
outputStack.Push(token);
}
}
while (opStack.Any())
{
outputStack.Push(opStack.Pop());
}
return Evaluate(outputStack.Reverse());
}
private IEnumerable<string> Tokenize(string input)
{
int start = 0;
input = input.Replace(" ", "");
for (int i = 0; i < input.Length; i++)
{
if (!char.IsDigit(input[i]) && input[i] != '.')
{
var token = input.Substring(start, i - start);
if (!string.IsNullOrWhiteSpace(token))
{
yield return token;
}
start = i + 1;
yield return input[i].ToString();
}
}
yield return input.Substring(start, input.Length - start);
}
private double Evaluate(IEnumerable<string> postfix)
{
var evalStack = new Stack<double>();
foreach (var element in postfix)
{
if (!String.IsNullOrWhiteSpace(element) && !precendence.ContainsKey(element))
{
evalStack.Push(double.Parse(element));
}
else
{
if (evalStack.Count == 0)
{
return 0;
}
else if (evalStack.Count == 1)
{
return evalStack.Pop();
}
var op2 = evalStack.Pop();
var op1 = evalStack.Pop();
double result;
switch (element)
{
case "+":
result = op1 + op2;
break;
case "-":
result = op1 - op2;
break;
case "/":
result = op1 / op2;
break;
case "*":
result = op1 * op2;
break;
default:
throw new NotSupportedException("operator is not supported");
}
evalStack.Push(result);
}
}
return evalStack.Pop();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment