Arrays, Matrices, Strings and other Data Structures.
Intro
TIBasic supports several types of useful datastructures. Complex numbers (not really data structuces, but they are excellent for use use as tuplets (pairs)), Strings, Matrices, and Lists (essentially arrays, but dynamically sized). Essentially every other data structure you need can be simulated using a combination of these. Here are what they can do, and what their limitations are. After you read through this I will explain some more interesting structures and how to represent them.Matrices
Overview
Matrices are used for storing real numerical data in a rectangular format.Pros
Matrices can be used to easily store and conceptualize data in a rectangular format.Cons
They are memory hogs. TIOS limits them to max dimensions of 99*99. You can't have more than 10 of them at a time ([A]
[J]
). They tend to be slow.
Limited to Real data. Can't really do anything that lists or strings can't.
Lists
Overview
Essentially dynamically sized arrays, lists allow you to easily store real or complex numerical data in linear format.Pros
Can store Real or Complex data. You can "attach" string based functions that apply a function to every piece of data in the list. You can use some simple arithmetic to "wrap" them into multiple dimensions (aka 2d, 3d, 4d, etc). Provided with default lists (L_{1}
L_{6}
) that can be used to take up less VAT space plus, you can define your own lists with 50602347 possible names.
These can be used as save files. Lists are also easily manipulable using the seq()
function.
Cons
Can't be longer then 999 elements. Still fairly slow. Limited to numerical data.Strings
Overview
Used for storing textual information, strings are little more than lists of tokens, however with a few tricks you can store numerical data as well.Pros
Strings tend to be very size efficient as each character/token takes a max of 2 bytes as opposed to lists and matrices which use 9. Like lists, they can be wrapped to have ndimensions, however unlike lists they are limited only by the available memory on your computer. They are also the fastest of the 3. Not only that but with the help ofinString()
, expr()
, length()
and sub()
you
can use them to store numeric data (in any base if you write a simple base converter).
Cons
limited to 10 of them...not really a limit if you use delimiters to pack them together..ummm....well...Input allows you to enter the " symbol into a string, but there's no way to test for it inprogram. other than that....well enough of my love affair with strings and back to the tutorialSets
A set is a collection of objects considered as a whole. The objects of a set are called elements or members. The elements of a set can be anything: numbers, people, letters of the alphabet, other sets, and so on. Sets are conventionally denoted with capital letters, A, B, C, etc. Two sets A and B are said to be equal, written A = B, if they have the same members. A set, unlike a multiset, cannot contain two or more identical elements. All set operations preserve the property that each element in the set is unique. Similarly, the order in which the elements of a set are listed is irrelevant, unlike a sequence or tuple.For those of you who don't understand that, essentially a set can be thought of as a list that only contains each element of the same value once. Our first project will be to implement a program that provides the basic set of set operations. I will work through the first 3 (add, remove, test for membership) with you and allow you to program the remaining ones (compare, union, difference, intersect) on your own. In the process we shall also begin to plan for robustness of code (graceful error handling and catching as many errors as possible before hand)
Okay, first thing here, we call a SetUpEditor so that we can reference
∟SET
without risk of an error.
:SetUpEditor ∟SET
Next off, this program requires 2 inputs, the list item to try an operation on, and a string command specifying which operation to perform.
Since strings a generally more valuable resources variable wise then numbers, this demo will store the number to use to I
and the command to
Ans
. There are other ways to do this, this one is somewhat simple, I recommend you think and come up with a more efficient way, its not hard.
The next thing to do is to try and make sure that we aren't deleting from or searching in a blank list. This means we need to check the dimension of the list, and the command being used.
:If "D"≠Ans and "A"≠Ans and not(dim(∟SET
:Then
:Pause "INVALID DIM
:Return
:End
Alright next thing to do here is to implement the first operation: Member. Basically, all this has to do is check if :Then
:Pause "INVALID DIM
:Return
:End
I
is in ∟SET
. Several ways (as usual to do that). The first way that comes to mind
is to use a for()
loop to loop through each element in the set, and check it that way. Unfortunately in BASIC
this is terribly inefficient. The next thing we could do to speed it up would be to use a seq()
command to accomplish the same thing.
Again this uses unnecessary clock cycles. We dont need anything complicated, just a simple comparison. If you'll remember however, must functions (including mathematical/boolean operators)
that accept numbers will also accept lists (what we are using to represent our set) and apply themselves to the whole list. Thus we can use an equals sign to do our job. Alas we must remember that our job
is not nearly that simple. Applying a normal operator to a list returns a list with the operator applied to each element. We must check the entire list if its 1 or 0. Fortunately the
max()
function returns the highest item in the list. Thus if there are any 1s (equalities) in the array, max()
will pick them out for us.
:If Ans="I
:Then
:max(I=∟SET
:Return
:End
Now for the next operation: Insert. Remember that sets must be composed of unique items?
That means we have to check if its already present in the set before adding. However if the the length of the set is zero
we shouldn't call :Then
:max(I=∟SET
:Return
:End
max()
for 2 reasons:
 It will raise an Invalid Dim error
 If its zero we can safely assume that the item isn't the list anyway
:If Ans="A
:Then
:If dim(∟SET
:Then
:0
:If max(I=∟SET
:Return
:End
:I→∟SET(1+dim(∟SET
:1
:Return
:End
The final operation I will teach you to implement is possibly the hardest of the 3: Remove. We must first detect
if the item is actually in the set. Then, if its there, we must delete it from the set. But how to go about this? Unfortunately
the TIOS doesn't support a remove command as one if its list operations. It does however allow you to assign new dimensions
to a list via dim. So shrinking a list's dimension by one should remove one item from the list, right? Right, but there's one caveat:
it will only remove the last item in the list. So what to do if thats not the one we want to remove? We must somehow find way to save that value
and put it back somewherepreferably where the item we want to remove is. That means we have to find the index of the item we want to delete,
copy the tail value in the list to its new location, and then shrink the list by one. Finally, just to be helpful we will also return whether or not
we actually successfully deleted anything.
:Then
:If dim(∟SET
:Then
:0
:If max(I=∟SET
:Return
:End
:I→∟SET(1+dim(∟SET
:1
:Return
:End
:If Ans="R
:Then
:If not(max(∟SET
:Then
:0:Return
:End
:seq(N(∟SET(N)=I),N,1,dim(∟SET
:max(Ans
:If Ans
:Then
:∟SET(dim(∟SET→∟SET(Ans
:dim(∟SET)1→dim(∟SET
:1
:Return
:End
:0
:Return
:End
:Then
:If not(max(∟SET
:Then
:0:Return
:End
:seq(N(∟SET(N)=I),N,1,dim(∟SET
:max(Ans
:If Ans
:Then
:∟SET(dim(∟SET→∟SET(Ans
:dim(∟SET)1→dim(∟SET
:1
:Return
:End
:0
:Return
:End
Assignment 1:
You will now implement the last 4 operations. Here's what you'll need to do, create a compare function that will return whether or not 2 sets (1 in∟SET
, 1 in ∟SET2
) are equivalent.
Note that order is not important in determining the equivalence of 2 sets. The next operation, Union should add the contents of ∟SET2
into the contents of ∟SET
while maintaining the property that no element should appear more than once in the result set.
Difference should remove any items that appear in ∟SET2
from ∟SET
. Intersect should delete all items from
∟SET
that do not appear in ∟SET2
. Starter code is here. For the contest: feel free to modify the existing routines
as long as you maintain the same functionality. And please send in those entries.
Stacks
In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls. Among other uses, stacks are used to run a Java Virtual Machine, and the Java language itself has a class called "Stack", which can be used by the programmer. The stack is ubiquitous.Essentially a stack works like this: to store something to it, you "push" the value onto the stack. To retrieve it, you "pop" it off. However, you can only access the top item at a top, so the last item in is the first out, and the first thing in is the last one out. You'll see why these are important later, but for now either accept that they are, or look them up on Wikipedia. Were going to work through a List based example here, then I'm going to have you write a program that evaluates postfix expressions using a stack.
Create the stack if isn't there yet, we don't want to end up with any errors about missing lists, and we don't want to have to trust our users to create it for us. There's a quote that goes something like this:
The history of the universe so far has been a race between programmers to create bigger and better foolproof programs, and the universe to create bigger and better fools. So far the universe is winning.When you program, always remember that quote and treasure it in your heart, or it WILL come back to haunt you. Anyway, call SetupEditor to create our stack:
:SetupEditor ∟STACK
Now we have to pop the top item in the stack and return it to I
. This is fairly simple,
you can use dim()
to get the size of the stack, and grab the last item in it.
:If Ans="POP
:Then
:If dim(∟STACK
:Then
:∟STACK(dim(∟STACK→I
Then it should be a simple matter to shrink the stack by getting the size using :Then
:If dim(∟STACK
:Then
:∟STACK(dim(∟STACK→I
dim()
, subtracting one,
and storing that back to the dim()
, right?
:dim(∟STACK)1→dim(∟STACK
:Return
Wrong! What happens if you try to pop of a stack that is empty? Normally this shouldn't happen,
but the user might make a mistake in their code and get confused by the TIOS's Invalid Dim errors. We want to give them something
informative so they can fix their code more easily. Remember this line: :Return
:If dim(∟STACK
?
Its designed to make sure the dim()
is nonzero.
Then we use this Else
clause to give them a nice friendly message
if it is zero.
:Else
:Disp "ERR:EMPTY STACK
:Stop
:End
:End
Now its time for push, and to introduce the concept of stack overflow. A stack is generally assigned limited space. If you try to push onto
a stack that is full, and the people who implemented the stack don't have some sort of error catching, you can write past the end of your assigned memory
and cause damage to other memory on the system, a technique often exploited by virus writers. Fortunately for us, the TIOS doesn't let Basic programs
do anything of that sort, and have even imposed a size limit on the length of lists (999). This means if we try to overflow our stack we will get an ugly
Invalid Dim error from the TIOS. Again its nice to provide our users with a better interface than that.
:Disp "ERR:EMPTY STACK
:Stop
:End
:End
:If Ans="PUSH
:Then
:dim(∟STACK
:If 999=Ans
:Then
:Disp "Stack Overflow
:Stop
:End
:I→∟STACK(1+Ans
:Return
:End
:Then
:dim(∟STACK
:If 999=Ans
:Then
:Disp "Stack Overflow
:Stop
:End
:I→∟STACK(1+Ans
:Return
:End
Assignment 2
You will now implement a String based postfix expression evaluation engine. You will be passed a string inAns
. You must then travel through the string. Any numeric values should be converted to string
on push on the stack. Any functions should pop the required arguments off the stack. If it takes multiple arguments it should
put the first value popped as the last argument, and the last value popped as the first argument. Push the result back once you've computed it. At the end of the program
pop off all remaining data and display it as a list (the first element should be the top, the last should be the bottom). Here's an example:
Code to run: "4 2 3 < 2 6 ?: 6 +"  
Stack at start  Stack after: "<"  Stack after: "2 6 ?:"  Stack after: "6 +"  Output 




{8,4 
 + add the top 2 stack entries
  subtract the first stack entry from the second stack entry
 / divide the second entry by the first entry.
 * multiply the top 2 entries
 ! factorial of the top entry
 = compare the top 2 entries with =
 ≠ compare the top 2 entries with ≠
 ≤ compare the top 2 entries with ≤
 ≥ compare the top 2 entries with ≥
 < compare
 > compare the top 2 entries with >
 AND, OR, XOR, NOT the normal boolean operators
 Degree set Degree mode, doesn't effect the stack
 Radian set Radian mode, doesn't effect the stack
 SINE return the sine of the top entry
 COSINE return the cosine of the top entry
 TAN return the tangent of the top entry
 MIN return the smaller of the top 2 numbers
 MAX return the larger of the top 2 numbers
 EXCH switch the top 2 numbers
 ?: if the third entry is nonzero, then return the second entry, else return the first entry