Arrays, Matrices, Strings and other Data Structures.

Table Of Contents || Next Tutorial

Intro

 TI-Basic 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. TI-OS 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 (L1-L6) 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 n-dimensions, 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 of inString(), 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 in-program. other than that....well enough of my love affair with strings and back to the tutorial

---

---

Sets

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.  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.  Alright next thing to do here is to implement the first operation: Member. Basically, all this has to do is check if 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.  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 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

 So our algorithm should work something like this: If the size of the set is non-zero, check if its in the set and add it accordingly. If the size is zero, just add it. One last touch: lets return a useful value for our users so they know if it was added or not, so give it a return value of either 1 or 0.  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 TI-OS 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 somewhere--preferably 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.

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 fool-proof 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:   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.  Then it should be a simple matter to shrink the stack by getting the size using dim(), subtracting one, and storing that back to the dim(), right?  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 TI-OS's Invalid Dim errors. We want to give them something informative so they can fix their code more easily. Remember this line: :If dim(∟STACK? Its designed to make sure the dim() is non-zero. Then we use this Else clause to give them a nice friendly message if it is zero.  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 TI-OS 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 TI-OS. Again its nice to provide our users with a better interface than that.

Assignment 2

 You will now implement a String based postfix expression evaluation engine. You will be passed a string in Ans. 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
3 2 4	1 4	2 4	8 4	{8,4

You must implement the following commands

• + --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 non-zero, then return the second entry, else return the first entry

---

---

TODO: Queues, Dictionaries

---

This site powered by Tomahawk CMS