| Assignment • FAQ • Development Guide • Code • Checklist • |
Question:
How should I associate priorites with each of the operators?
Answer:
You should associate a priority with each operator as follows:
| ! | 8 |
| ^ | 6 |
| * / | 4 |
| + - | 2 |
| ( | 0 |
During the process of checking for character input, if a character array is set up called "operators" that is filled "()+-*/^ !" then the precedence of the operators becomes the index in the operator array with the least significant bit of the index set to zero. The priority of the operator should be stored along with the ASCII code for the operator as separate bytes all in one word. Also, although the human eye can distinguish numbers from operators, the computer cannot make this distinction. Therefore, you must program the computer to be able to tell the difference between numbers and operators. This information should also be stored within the same word as the ASCII code and priority.
Question:
I know you went over the function setupword in class, but I still don't quite understand what is going on. Can you go over it again?
Answer:
The main idea behind setupword is to create values for operators that can be stored on your stack. These operator value must be distinct from the positive numbers that can also be on your stacks at the same time.
At the time when numbers and operators can co-exist on the same stack, all numbers are positive and all operators can therefore be negative. This way, for any stack item, your program can distinguish between the them.
The value for the operators should have everything associated with that operator: a distinction from numbers, the index in the functions array corresponding to that operator, the priority of the operator and the ASCII code.
We saw in class that the priority of the operator can be attained from its index. Therefore, in class I suggested that setupword return a value containing the sign-bit set to '1', the index in the next-to-rightmost byte, and the ASCII character in the rightmost byte.
Therefore for '+', you'd have:
0x800000000000022B
where:
the first 8 above in binary is: 1000 (the sign bit is set),
the next to rightmost byte is: 02 (the index),
the rightmost byte is: 2B (the ASCII code for plus).
Question:
Can someone please explain to me what getPriority () and getOperator () methods really mean in the Calc.java file?
Answer:
Really technical answer:
They're methods designed to get information back out from the values that setupword returns by performing the reverse operations.
Less technical answer:
They are methods that take a given input (a word, which for us, is also a long) and morph it into a given form of output that has some utility to us.
Really long answer answer that is recommended for everyone to read:
Our calculator is based on a stack, which is itself based on an array. This array basing means that the stack can only store one class of values -- longs, in this case. The stack, however, needs to store both operators and operands. You should recall from hw1 that the characters for operators are represented in memory by their ASCII values, which are ints. Thus, technically, we could just drop the operator characters onto the stack and store them that way. This presents us with an insurmountable problem, however -- once everything is on the stack, how do we know the difference between an operator and the user entering its ASCII value as an operand? Both are represented as numbers, and there's no line of demarcation that allows us to tell the difference.
Clearly, then, we need a clever solution to an interesting problem. Our solution? The calculator can only deal with positive numeric input, and we will manually set all operators to have negative memory representations. How? Enter setupword() and bit manipulation.
Self-test time. Do you understand bit manipulation and its abilities? If not, go to Google and look up the AND (&), OR ( | ), and SHIFT (<< and >>) operators (XOR and signed SHIFT and whatnot are all useful too, but we're not using them here). The important thing to know for now is that AND'ing with 1's allows us to pull a desired bit pattern out, OR'ing with 0's copies a bit pattern, and SHIFT allows us to move a bit pattern to a desired location.
Now, look at the code for setupword() -- the return line, specifically (you were given this in class). Do you understand what it's doing? Basically, it's custom-constructing a return result. You've got a sign bit (0x8000000000000000, which in binary, is 1 followed by 63 0's) which is being OR'ed with the ASCII for the operator's character (which is always 256 or less, meaning it will only take up the rightmost byte), which is also being OR'ed with the index in the functions array left-shifted by a byte. In other words, you're making this:
| Bytes: | 1-2 | 3-4 | 5-6 | 7-8 |
| Content: | SIGN | 0x00 | INDEX | CHAR |
This is the size in memory of a single long (and is assigned that type by the return type of setupword() ), but it contains all the information we might ever need on that operator.
So now we go around and la-dee-da with intopost(), and it comes time that we go "Hey, I've got this operator here, and I'd really like to do
Recall, the AND operator allows us to copy a desired bit pattern. So lets say that we want to get the ASCII value for the operator's character back out of the encoded long. We know that the ASCII code goes in the least significant byte... so that's the one we want to copy. Thus, what we want to do is to AND with 0x00 00 00 FF. FF happens to be the hex for 255, which in binary terms, is 1111_1111. The 0's will prevent us from pulling any of the information in the first three bytes, leaving us with only the character part.
getIndex does the same thing. It masks with 0x00 00 FF 00 to pull out the index byte, then right-shifts by 8 bits to move the information back into the least significant byte (remember, we moved it 8 bits to the left in setupword() ).
PRIORITY does basically the same thing as INDEX, but with the minor difference of using 0xFE instead of 0xFF. This is a nifty trick that basically says "If the number is even, don't touch it. If the number is odd, subtract 1 from it to make it even." This trick works when combined with the special ordering in the operators[] and functions[] arrays (the blank spot in operators[], and the NULLs in functions[]). Notice that we don't bother right-shifting here. We could, but it's unnecessary -- I don't care if the priorities are 0,2,4,6,8 or 100000,100002,100004, etc, as long as they are equal when they should be equal and greater/lesser when they should be.
Hope that helps.
Question:
I am working on the factorial function and noticed that it had two parameters. I did this function recursively as talked about in class, and i never used the variable ignored. Why do i need this variable?
Answer:
You don't. That's why it's called "ignored" -- the parameter is ignored entirely.
To forestall the obvious next question, "Why is the parameter there if it doesn't do anything?", take a look at the functions[] array. Note that it is prototyped as:
interface Operation {
long operation(long op1, long op2);
}
This is basically a way for us to create an array of functions. This array is really empowering, as you'll come to understand when the usefulness of setupword(), the operators[] array, and the functions[] array all click together in your head (assuming you don't completely understand already, which you may) while writing eval(). If you've written eval() and still don't completely get the simplicity of it all, ask one of the tutors in the lab, and they can explain exactly what's going on and why.
Anyways. The point is -- each function in that functions[] array must have an identical prototype. For fact() to be a member of that array requires it, too, to have two long parameters... despite the fact that it only really needs to have one operand. Thus, we set it up with an "ignored" parameter.
This solution approach may at first look like bad programming practice (and to a certain extent, it really kind of is). However, in this situation, there's really no demonstrably better alternative. There are other solutions, of course, but every one of them that I've ever seen incorporates elements of poor practice in its own right. This is just the one that was chosen to go with.
| Assignment • FAQ • Development Guide • Code • Checklist • |