Using Stacks - Lua and Objective-C
If you are new to development or do not come from a Computer Science background then the mere mention of stacks would mean anything piled on top of another, like a stack of books or crates or even like the image Money, something that all developers would like to have once they complete their application.
Today I came across a small problem, more so a puzzle to solve. The issue at hand is more so like a stack calculator, if you have heard about the RPN calculators. Where the numbers are added to a stack and then the operand initiates the calculations. In short, if one were to have an input like
1 2+4*7 1+2*8*+ it would result in 140 and it can be understood thus+-----+--------------+ |CHAR | Result | +-----+--------------+ | | Empty | | 1 | 1 | | 2 | 1, 2 | | + | 3 | | 4 | 3, 4 | | * | 12 | | 7 | 12,7 | | 1 | 12, 7, 1 | | + | 12, 8 | | 2 | 12, 8, 2 | | * | 12, 16 | | 8 | 12, 16, 8 | | * | 12, 128 | | + | 140 | +-----+--------------+
Now from an algorithmic point this is quite simple to achieve
How to run a stack calculator
We iterate through the string passed character by character and if it is a digit (0 .. 9) then we add it to the stack and if it is a operator, we calculate according to the operand. One thing we need to note is that for the operand there needs to be two numbers that we can operate on. In case we do not get two numbers the result is -1 and the processing stops.Step 1 - The Stack
First we need to create a stack which will hold all of the digits that are passed and then perform the calculations when an operand is passed. For a stack to work we also need to have two functions, pop and push, where push adds a digit to the stack and pop removes it off the stack. We can declare the functions aslocal stacks = {} -- create a stack
function push(theChar)
table.insert(stacks, theChar)
end
function pop()
local theLen = #stacks
local theRet = stacks[theLen]
table.remove(stacks, theLen)
return theRet
end
This is easier to manage in Lua than in other languages
Step 2 - Processing character by character
Now we shall process the string that is passed and access each characterlocal _str = "12+4*71+2*8*+" for i=1, #_str do print(_str:substr(i,i)) end
If we run this code, we can see each character displayed on screen.
Now we need to process these or add the digits to the stacks using the
push function aslocal _str = "12+4*71+2*8*+"
local _chr = nil
for i=1, #_str do
_chr = _str:sub(i,i)
if _chr == "+" then
-- Add
elseif _chr == "*" then
-- Multiply
else
push(_chr)
end
end
Step 3 - Handling Add and Multiply
We can add the add and multiply functions to the code above likefunction stack_machine(theCode)
local _chr = nil
local res = 0
local d1, d2
for i = 1, #theCode do
_chr = theCode:sub(i, i)
if _chr == "+" then
d1, d2 = pop(), pop()
if d1==nil or d2==nil then
return -1
end
push(d1+d2)
elseif _chr == "*" then
d1, d2 = pop(), pop()
if d1==nil or d2==nil then
return -1
end
push(d1*d2)
else
push(_chr)
end
end
return pop()
end
Now we can call the function and also display the result with
print(stack_machine("12+4*71+2*8*+")) --> 140
print(stack_machine("12++")) --> -1
For the Reader
This was made with the simplicity of just + and *, if you so wish you can extend this further you can also add the functionality to include subtraction and division or other operands. If you feel you need more of a challenge then you can handle numbers rather than digits, so 12 is not 1 and 2, but 12 and consider the space as a separator. So 12 3+4*5+ would equate to+-----+--------------+ |NOS | Result | +-----+--------------+ | | Empty | | 12 | 12 | | 3 | 12, 3 | | + | 15 | | 4 | 15, 4 | | * | 60 | | 5 | 60,5 | | + | 65 | +-----+--------------+
Using this in Objective-C
You can see why Lua is such a treat to use, it is simple and fast to use. If you were to use Objective-C this would have been so much longer and more complex, where the stacks would be an NSMutableArray. The largest issue while using Objective-C is the conversions between the data types, from NSString to int and so on, even simple comparisons are hardly simple.
a rough conversion of the stacks in Objective-C would look like
NSMutableArray *stacks;
void push(NSString *digit){
[stacks addObject:digit];
}
int pop(){
NSInteger lenStack = [stacks count];
if (lenStack <= 0) {
return -1;
}
int res = [[stacks objectAtIndex:lenStack-1] intValue];
[stacks removeLastObject];
return res;
}
As you can see that it is rather inconvenient using Objective-C. One more thing is that the stacks has not been initialized and needs to be initialized and we do so in the function stack_machine which is declared as
int stack_machine(NSString *S]{
stacks = [NSMutableArray new];
for (int i=0; i<[S length];i++)
{
NSString *chr = [S substringWithRange:NSMakeRange(i,1)];
if ([chr isEqualToString:@"+"])
{
int d1 = pop();
int d2 = pop();
if (d1!= -1 && d2!= -1){
push([NSString stringWithFormat:@"%d", d1+d2]);
}else{
return -1;
}
}else if ([chr isEqualToString:@"*"]){
int d1 = pop();
int d2 = pop();
if (d1!= -1 && d2!= -1){
push([NSString stringWithFormat:@"%d", d1*d2]);
}else{
return -1;
}
}else{
push(chr);
}
}
int res = pop();
[stack removeAllObjects];
[stack release];
return res;
}
As you can see that the Objective-C version is a bit complex as compared to the Lua version which is so much simpler to use. While one can compare strings or numbers in Lua by simply using the '==' operator, in Objective-C since NSStrings are not string but objects, one has to use the isEqualToString followed by a fixed string which is indicated by the use of a '@'. Since the functions accept only particular datatypes and there is no coercion as provided in Lua, one has to use the members of the object to convert to a particular datatype. All of this maybe for another tutorial soon.
Note: There could be a much better Objective-C implementation, this was to show a transition of an equivalent manner to translate the Lua code to Objective-C for comparison.
A smaller and more concise function (written in Lua) without the use of stacks can be found here
Comments
Post a Comment