Created
September 11, 2014 12:20
-
-
Save ikkentim/aae69196e5bf2ec16d96 to your computer and use it in GitHub Desktop.
Simple postfix calculator, including a infix to postfix converter.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
namespace Calculator | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
const string infix = "(11*22)+5--(200/10)"; | |
var postfix = Calculator.InfixToPostfix(infix); | |
var result = Calculator.CalculatePostfix(postfix); | |
Console.WriteLine("{0} >>> {1} === {2}", infix, string.Join(" ", postfix), result); | |
Console.ReadLine(); | |
} | |
public static class Calculator | |
{ | |
private static readonly Operator[] Operators = | |
{ | |
new Operator('-', stack => | |
{ | |
if(stack.Count == 1) stack.Push(-stack.Pop()); | |
else if (stack.Count > 1) | |
{ | |
var b = stack.Pop(); | |
var a = stack.Pop(); | |
stack.Push(a - b); | |
} | |
else | |
{ | |
throw new Exception("stack corrupted"); | |
} | |
}), | |
new Operator('+', stack => | |
{ | |
if (stack.Count > 1) | |
{ | |
var b = stack.Pop(); | |
var a = stack.Pop(); | |
stack.Push(a + b); | |
} | |
else if(stack.Count == 0) | |
{ | |
throw new Exception("stack corrupted"); | |
} | |
}), | |
new Operator('/', stack => | |
{ | |
if (stack.Count > 1) | |
{ | |
var b = stack.Pop(); | |
var a = stack.Pop(); | |
stack.Push(a / b); | |
} | |
else | |
{ | |
throw new Exception("stack corrupted"); | |
} | |
}), | |
new Operator('*', stack => | |
{ | |
if (stack.Count > 1) | |
{ | |
var b = stack.Pop(); | |
var a = stack.Pop(); | |
stack.Push(a * b); | |
} | |
else | |
{ | |
throw new Exception("stack corrupted"); | |
} | |
}), | |
new Operator('^', stack => | |
{ | |
if (stack.Count > 1) | |
{ | |
var b = stack.Pop(); | |
var a = stack.Pop(); | |
stack.Push((int)Math.Pow(a, b)); | |
} | |
else | |
{ | |
throw new Exception("stack corrupted"); | |
} | |
}), | |
new Operator('%', stack => | |
{ | |
if (stack.Count > 1) | |
{ | |
var b = stack.Pop(); | |
var a = stack.Pop(); | |
stack.Push(a % b); | |
} | |
else | |
{ | |
throw new Exception("stack corrupted"); | |
} | |
}), | |
}; | |
public static int CalculatePostfix(IEnumerable<string> input) | |
{ | |
var operandStack = new Stack<int>(); | |
foreach (var i in input.Where(i => i.Length != 0)) | |
{ | |
/* | |
* Push numbers to the operand stack. | |
*/ | |
int num; | |
if (int.TryParse(i, out num)) | |
{ | |
operandStack.Push(num); | |
continue; | |
} | |
/* | |
* Execute operators. | |
*/ | |
Operators.First(o => o.Symbol == i[0]).Action(operandStack); | |
} | |
/* | |
* Last number in the stack is the result. | |
*/ | |
return operandStack.Pop(); | |
} | |
public static int CalculateInfix(string input) | |
{ | |
return CalculatePostfix(InfixToPostfix(input)); | |
} | |
public static IEnumerable<string> InfixToPostfix(string input) | |
{ | |
var operatorStack = new Stack<char>(); | |
var numberStack = string.Empty; | |
var depth = 0; | |
/* | |
* Remove some issues (double negatives) | |
*/ | |
string tmp = input.Replace("--", "+"); | |
while (tmp != input) | |
{ | |
input = tmp; | |
tmp = input.Replace("--", "+"); | |
} | |
foreach(var c in input) | |
{ | |
/* | |
* Numeric characters should be put in the number stack. | |
* Then proceed to the next character. | |
*/ | |
if (c >= '0' && c <= '9') | |
{ | |
numberStack += c; | |
continue; | |
} | |
/* | |
* If there are numbers left in the number stack we know | |
* it is a complete number and can be moved to the output. | |
*/ | |
if (numberStack.Length > 0) | |
{ | |
yield return numberStack; | |
numberStack = string.Empty; | |
} | |
/* | |
* Opening of closures should be pushed to the stack. When we enter a closure, | |
* we need to increase the closure depth. | |
*/ | |
if (c == '(') | |
{ | |
operatorStack.Push('('); | |
depth++; | |
/* | |
* All further checks will never be true, hence we can continue to next character. | |
*/ | |
continue; | |
} | |
/* | |
* When we reach the end of a closure, all operators pushed to the stack from within | |
* the current closure can be pushed to the output. At this point we can also decrease | |
* the closure depth. | |
*/ | |
if (c == ')') | |
{ | |
var o = operatorStack.Pop(); | |
while (o != '(') | |
{ | |
yield return new string(o, 1); | |
o = operatorStack.Pop(); | |
} | |
depth--; | |
} | |
/* | |
* If we reach 0 depth at this point, we need to send the whole operator stack to the output. | |
*/ | |
if (depth == 0) | |
while (operatorStack.Any()) | |
yield return new string(operatorStack.Pop(), 1); | |
/* | |
* Send all new operators to the operator stack. | |
*/ | |
if (Operators.Any(o => o.Symbol == c)) | |
operatorStack.Push(c); | |
} | |
/* | |
* Send all remaining operators to the output. | |
*/ | |
while (operatorStack.Any()) | |
yield return new string(operatorStack.Pop(), 1); | |
} | |
/// <summary> | |
/// Contains information about a certain operator. | |
/// </summary> | |
private struct Operator | |
{ | |
public Action<Stack<int>> Action { get; private set; } | |
public char Symbol { get; private set; } | |
public Operator(char symbol, Action<Stack<int>> action) : this() | |
{ | |
if (action == null) | |
throw new ArgumentNullException("action"); | |
Symbol = symbol; | |
Action = action; | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment