In my sample, I've decided to create a flash calculator. This calculator will take a formulae, and once the user presses the equal sign, will show the results.
Well, like in about everything programming, there can be arguments about how the "best" way to do this sort of thing, but I'll just go with the way that I think was a good way to go.
I think the best way to start is with your basic stack; a stack of "formula tokens." Think of what makes up a formula: numbers, operators, and parentheses. So we use the stack to build them. Normally, I would like to use a stack object, but since I couldn't find one already made, I decided to use an "ArrayCollection" as my stack object.
Tokenizing
However, there are some user interface considerations. While the operators are individual characters, the numbers themselves are built one digit at a time, and might include a period. So we need an intermediate stack of characters, with digits and operators. Therefore, as the user presses each button, a value would be "pushed" onto the top of the stack (in my case, added to the end of the array) one character at a time. Once the formula is complete, we will work on the evaluation of the formula itself.
Now, evaluating the formula must start with converting the array of characters that we have into a group of the tokens. This mostly involves combining the digits into numbers, and seperating out the operators. Here's the code that I used to seperate things out:
for (var x:int=0;x<formulae.length;x++)
{
if (isNaN(formulae[x]) && formulae[x] != ".")
{
if (tmpStr.length > 0)
{
LastNumber = Number(tmpStr);
tmpStr = "";
sc.addItem(LastNumber);
}
sc.addItem(formulae[x]);
}
else
{
tmpStr += formulae[x];
}
}
if (tmpStr.length > 0)
{
LastNumber = Number(tmpStr);
sc.addItem(LastNumber);
}
The key point to this idea is the function "is not a number" or isNaN. We are assuming that each token is seperated by an operator, and therefore, we will tack each digit together until we run into an operator, with the exception of a dot that can appear in a number. (Special Note: Obviously, this is a perfect spot to check the number to see if there isn't already a dot in the number to prevent a duplicate. However, in my application we are going to assume a valid input. In other words, "garbage in garbage out; diamonds in diamonds out"). If the digit is a number or a dot, we add it to a temporary string. Otherwise, it's an operator, so we convert the temporary string to a number, and add it to the stack (assuming it isn't blank, which could happen), and then add the operator to the stack. In the end, we result with a proper tokenized stack, and we're ready to start processing.
RPN
The next thing that I've decided to do is to process the formula as a postfix reverse polish notation. Don't ask me why it's called that. But I will say it is much easier to evaluate than most other ways you might want to resovle something like a formula. The process even makes it easier to get "priority" done correctly, where multiplication takes place before addition.
So here is the code for this portion of the code which creates a new stack in reverse polish notiation:
for(x=0;x<sc.length;x++)
{
if (!isNaN(sc[x]))
{
stack.addItem(sc[x]);
}
else
{
switch(sc[x])
{
case "(": tmpStack.addItem(sc[x]);
break;
case ")":
while (tmpStack.length > 0 && (tmpStack[tmpStack.length-1] != "("))
{
stack.addItem(tmpStack[tmpStack.length-1]);
tmpStack.removeItemAt(tmpStack.length-1);
}
tmpStack.removeItemAt(tmpStack.length-1);
break;
case "-":
if (tmpStack.length > 0 && (tmpStack[tmpStack.length-1] == "+" tmpStack[tmpStack.length-1] == "*" tmpStack[tmpStack.length-1] == "^" tmpStack[tmpStack.length-1] == "/" tmpStack[tmpStack.length-1] == "%"))
{
stack.addItem(tmpStack[tmpStack.length-1]);
tmpStack.removeItemAt(tmpStack.length-1);
}
tmpStack.addItem(sc[x]);
break;
case "+":
if (tmpStack.length > 0 && (tmpStack[tmpStack.length-1] == "-" tmpStack[tmpStack.length-1] == "*" tmpStack[tmpStack.length-1] == "^" tmpStack[tmpStack.length-1] == "/" tmpStack[tmpStack.length-1] == "%"))
{
stack.addItem(tmpStack[tmpStack.length-1]);
tmpStack.removeItemAt(tmpStack.length-1);
}
tmpStack.addItem(sc[x]);
break;
case "^": tmpStack.addItem(sc[x]);
break;
case "*":
if (tmpStack.length > 0 && (tmpStack[tmpStack.length-1] == "^" tmpStack[tmpStack.length-1] == "/" tmpStack[tmpStack.length-1] == "%"))
{
stack.addItem(tmpStack[tmpStack.length-1]);
tmpStack.removeItemAt(tmpStack.length-1);
}
tmpStack.addItem(sc[x]);
break;
case "%":
if (tmpStack.length > 0 && (tmpStack[tmpStack.length-1] == "^" tmpStack[tmpStack.length-1] == "/" tmpStack[tmpStack.length-1] == "*"))
{
stack.addItem(tmpStack[tmpStack.length-1]);
tmpStack.removeItemAt(tmpStack.length-1);
}
tmpStack.addItem(sc[x]);
break;
case "/":
if (tmpStack.length > 0 && (tmpStack[tmpStack.length-1] == "^" tmpStack[tmpStack.length-1] == "*" tmpStack[tmpStack.length-1] == "%"))
{
stack.addItem(tmpStack[tmpStack.length-1]);
tmpStack.removeItemAt(tmpStack.length-1);
}
tmpStack.addItem(sc[x]);
break;
}
}
}
if (tmpStack.length > 0)
{
for(x=tmpStack.length-1;x>=0;x--)
stack.addItem(tmpStack[x]);
}
This part takes some getting used to. Think about our three different stacks. The first stack has the formulae in the "infix" notation. The second one will contain the operators temporarily. The last will hold the actual reulting RPN formula.
So, if we run into a number, we automatically push that to the end of the results stack. If we find an operator, we have to work through do we push it to the results or push it to the operator stack. (This part is the one you need to pay attention to, cause it is hard to wrap around into words) Notice that we push things to the temporary stack mainly to hold them in order to allow the "priority" operators to be pushed on the stack before the lower "priority" operator. This is done with the check to see what operator appeared prior to it. This sifting naturally turns 3+6*2 into 362*+.
Evaluation
So lets take a look at that last formula. 3 6 2 * +. We first take the 3 and push it onto the stack. Next we take the 6 and push it onto the stack. Next we put the 2 onto the stack. No actions yet. NOW... we have an operator, the multiplication. So we pop off two values from the stack and execute that operator, pushing the result of that operation back onto the stack.
Here's the code:
for(x=0;x<stack.length;x++)
{
if (!isNaN(stack[x]))
tmpStack.addItem(stack[x]);
else
{
LastNumber = tmpStack[tmpStack.length-1];
tmpStack.removeItemAt(tmpStack.length-1);
ThisNumber = tmpStack[tmpStack.length-1];
tmpStack.removeItemAt(tmpStack.length-1);
switch(stack[x])
{
case "+":
tmpStack.addItem(ThisNumber + LastNumber);
break;
case "-":
tmpStack.addItem(ThisNumber - LastNumber);
break;
case "*":
tmpStack.addItem(ThisNumber * LastNumber);
break;
case "/":
if (LastNumber != 0)
tmpStack.addItem(ThisNumber / LastNumber);
else
tmpStack.addItem(0);
break;
case "%":
if (LastNumber != 0)
tmpStack.addItem(ThisNumber % LastNumber);
else
tmpStack.addItem(0);
break;
case "^":
tmpStack.addItem(Math.pow(ThisNumber, LastNumber));
break;
}
}
}
Result = tmpStack[tmpStack.length-1];
Other Ideas
Oviously there are ways to improve this app. Most glaring is the idea of filtering the input to prevent garbage functions. Another idea is to check stack underflow's (too few operators) or overflows (too many operators not enough values).
Feel free to comment on this app. I'll post the full source code if I can feel confident enough about it.
