Expression Evaluation Problem
I came across this problem (I am unwilling to share the source, however this might be helpful in a wrong way to some fellows). So, the crux is, design/suggest improvements over a given code for a given scenario.
C# Coding/Design Task
A junior member of your team has been asked to create a simple calculation module
(and related tests) that can process arithmetic commands with the input specification:
Grammar:
cmd::= expression* signed_decimal
expresion::= signed_decimal ' '* operator ' '* operator::= '+' | '-' | '*'
signed_decimal::= '-'? decimal_number
decimal_number::= digits | digits ‘.’
digits digits::= '0' | non_zero_digit digits*
non_zero_digit::= '1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
He has produced the following Code. What changes will you suggest? Please consider the quality of the solution (including the design), and provide an updated version of the code, applying your suggestions.
Given Version of Code:
Calculator.cs
using System;
namespace Calculator
{
///<summary>
///Basic calc engine for handling +, -, * operations.
///</summary>
public class CalcEngine
{
///<summary>
///Process a calculation command string
///</summary>
///<param
name="p">cmd</param>
///<returns></returns>
public string Process(string p)
|
|
{
|
|
String[] stuff
= p.Split(' ');
|
|
double result =
0;
|
|
bool nextOpAdd
= false;
|
|
bool nextOpSubtract
= false;
|
|
bool nextOpMultiply
= false;
|
|
foreach (string x in stuff)
|
|
{
|
|
try
|
|
{
|
|
double nextVal
= Double.Parse(x);
|
|
if (nextOpAdd)
|
|
result += nextVal;
|
|
else if (nextOpSubtract)
|
|
result -= nextVal;
|
|
else if (nextOpMultiply)
|
|
result *= nextVal;
|
|
else
|
|
result = nextVal;
|
}
|
catch
|
|
{
|
|
nextOpAdd = false;
|
nextOpSubtract = false; nextOpMultiply = false;if (x == "+")
nextOpAdd = true;else if (x == "-")
nextOpSubtract = true;else if (x == "*")
nextOpMultiply = true;
}
}
return result.ToString();
}
}
}
//-------------------- This is the NUnit Test Class ------------------//
using Calculator;
using NUnit.Framework;
namespace TestCalculator
{
[TestFixture]
public class CalcEngineTest
{
[Test]
public
void Test()
{
CalcEngine engine = new CalcEngine(); System.Console.WriteLine(engine.Process("1 +
2"));
}
}
}
Solution
Design:
Given
Grammar:
cmd::=
expression* signed_decimal
expresion::=
signed_decimal ' '* operator ' '* operator::= '+' | '-' | '*'
signed_decimal::= '-'? decimal_number decimal_number::=
digits | digits ‘.’ digits digits::= '0' | non_zero_digit digits*
non_zero_digit::= '1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
Assumption:
Signed Decimal and Operator may not be separated by spaces. i.e. 5+2-3 * 6+ 2 is a valid scenario and it
should evaluate to 26.
Based
on my understanding of the Given Predicate/Grammar & from the given code
I have
the following observations:
- Developer code is based on a strict rule that operands and operators will be separated by space
- (that’s why use of .Split(‘ ‘) ). This may not be true and should be able to handle variety of inputs.
- All the code lies within one method (Process()), which may grow unmaintainable.
- One Boolean variable for each operation has been used, Design is not flexible/adaptable for addition of more operators (like divide, square root etc.)
- Code has operator detection logic handled in Catch block. Actually, catch block shouldn’t be used for input verification purpose.
- Program State is not being maintained, as all code is within single method.
- Generation of test suites/cases for such code is little tricky.
- No naming conventions were followed.
- Use logical and contextual names for local variables
- Use variable/object pooling as and when possible instead of creating local variables.
Suggestions:
- Modularize code into logical units (classes) [as shown in code below]
- Return proper/informative error codes/messages as and when needed.
- Maintain state of the application using classes/objects
- Though I too have used ForEach loop, but For performs better, so this program can be tuned more for performance
- Modularized code is better maintainable, readable and extendable
- Usage of Switch construct instead of if else if makes code flexible for future modifications
- CCommand class manages the user input and has a property that will store computed Result.
- CBetterCalcEngine class manages state of the Calculation Engine/Application
- TryParse has been used instead of Parse.
namespace BetterCalculator
{
class Program
{
static void Main(string[] args)
{
CCommand cmdObj = new
CCommand("1
+ 2 + 3+4+5");
CBetterCalcEngine myEngine = new CBetterCalcEngine(cmdObj);
EErrorCodes eCode = myEngine.Compute();
}
}
// Instead of a bool for each operator, using delegate
public delegate double ExpressionOperators(double op1, double
op2);
public enum EErrorCodes
{
NoError,
InvalidCommandString,
InvalidOperands,
InvalidOperation,
DivideByZero,
}
public class CBetterCalcEngine
{
//Using Customized logic of Expression Evaluation
//Traverse the user input expression from Left to Right
//If you encounter Operand (Multi-Digit), push into Stack
//If you encounter Operator, Enqueue into a Queue
private CCommand
InputCommand;
private Stack<double>
OperandStack;
private Queue<char>
OperatorQueue;
public CBetterCalcEngine(CCommand
userCommand)
{
InputCommand
= userCommand;
OperandStack
= new Stack<double>();
OperatorQueue
= new Queue<char>();
}
public EErrorCodes
Compute()
{
double nextOperand = 0, result = 0, op1, op2;
OperandStack.Clear();
OperatorQueue.Clear();
string operand = string.Empty;
foreach (char opChar in InputCommand.Command)
{
if (opChar == ' ')
{
continue;
}
if (InputCommand.IsValidOperator(opChar) == false)
{
operand
+= opChar;
}
else
{
if (Double.TryParse(operand,
out nextOperand) == false)
{
return EErrorCodes.InvalidOperands;
}
OperandStack.Push(nextOperand);
OperatorQueue.Enqueue(opChar);
operand = string.Empty;
if (OperandStack.Count == 2)
{
op1
= OperandStack.Pop(); op2 = OperandStack.Pop();
ExpressionOperators operation =
InputCommand.GetOperation(OperatorQueue.Dequeue());
if (operation != null)
{
result
= operation(op2, op1); OperandStack.Push(result);
}
else
{
return EErrorCodes.InvalidOperation;
}
}
}
}
if (OperandStack.Count == 1 &&
OperatorQueue.Count > 0)
{
if (Double.TryParse(operand,
out nextOperand) == false)
{
return EErrorCodes.InvalidOperands;
}
OperandStack.Push(nextOperand);
operand = string.Empty;
if (OperandStack.Count == 2)
{
op1
= OperandStack.Pop(); op2 = OperandStack.Pop();
ExpressionOperators operation =
InputCommand.GetOperation(OperatorQueue.Dequeue());
if (operation != null)
{
result
= operation(op2, op1); OperandStack.Push(result);
}
else
{
return EErrorCodes.InvalidOperation;
}
}
}
else
{
return EErrorCodes.InvalidOperands;
}
InputCommand.Result =
OperandStack.Pop().ToString(); return EErrorCodes.NoError;
}
}
public class CCommand
{
//Stores user Input Command/Expression
public string Command
{ get; set; }
//Computed Result of the Command/Expression
public string Result
{ get; set; }
//For future extension. Add new operator to this Variable
public string
ValidOperators = "+-*";
public CCommand(string
commandString)
{
Command
= commandString; Result = string.Empty;
}
public bool
IsValidOperator(char opChar)
{
return ValidOperators.Contains(opChar);
}
public ExpressionOperators
GetOperation(char currentOpertor)
{
// For future extension. Add Case for the new operator here
switch (currentOpertor.ToString())
{
case "+":
return AddOperation;
case "-":
return SubstractOperation;
case "*":
return MultiplyOperation;
default:
return null;
}
}
private double
AddOperation(double op1, double op2)
{
return op1 + op2;
}
private double
SubstractOperation(double op1, double op2)
{
return op1 - op2;
}
private double
MultiplyOperation(double op1, double op2)
{
return op1 * op2;
}
// For future extension. Add Handler Method for the new
operator here
}
}
·This code can still be tuned/refined for performance
·Try Catch block exception
handling can be employed.
No comments:
Post a Comment