Calculator using 2 stacks

Question

Hi all. I have an intel assembly assignment. I need to write a calculator which uses 2 stacks. For example, i have an expression like 23+4/2^4$ .So that $ indicates the end of expression. What I will do is to have two stacks, one for numbers, one for operators and push and pop them according to the operator precedence.

What I need is how can I use 2 stacks for two different purpose at the same time. As long as I know esp register indicates the place for variables in the stack to pop the last or to push a new one. But if I only have one esp register, how can I have two stacks?

Thanks in advance...

Answer 1

I think what you're looking for is Dijkstra's shunting algorithm.

I have solved it without using stacks during interpretation, only during execution as described in my blog.

As for making extra stacks, it is quite easy. All a stack is, is really just an area of memory with a pointer to the top and bottom. Every time you push, you increment the top pointer, every time you pop you decrement the top pointer.

Answer 2

Since your two stacks are not independent, another idea would be to interleave the data on a single stack. For example, you could use even-numbered words for numbers and odd-numbered words for operators.

---

Edit: elaborating on the idea as requested in comment: I believe that every time you push an operator, you are then going to push the number that follows it (because that number in turn might be followed by an operator of higher precedence). Similarly, every time you pop and operator, you are going to pop two operands and push a result. So the operator stack and the operand stack grow and shrink in tandem, and since the original question was how to do this in assembly code, I suggested they could share alternating slots on a single stack. (If that's not sufficient elaboration, please let me know and I will edit again.)

Answer 3

So, am I right to create two stacks like this:

mov ecx,256
L1: call ReadInt
    push eax          ;push the integer to where esp=1 points
    add esp,ecx       ;esp=1+256=257, now esp points to 257.

    call ReadChar     ;read operand
    cmp al,endChar    ;compare with end sign=$
    je next       
    push al           ;push operand to where esp=257 points
    sub esp,ecx       ;esp=257-256=1, now esp is in the original position
    loop L1
next:
...

Of course the comments are for the first loop.

BTW, I got an "1>..\main.asm(46) : error A2149:byte register cannot be first operand" error for (push al)? what's the matter?

thanks...

Answer 4

suppose the expression has length L , then each of your stacks will be at most L, so you will need at the most 2L memory.
increase ESP by 2L , at ESP you will have the beggining of your first stack,at ESP+L you will have the beggining of your second stack(it should be noted that neither of these stacks will ever exceed L beacause the expression is of length L).
The shunting yard algorithm can be found in various places.What it does is the conversion from infix notation
to postfix notation. After that the evaluation of the postfix notation will not be hard.

Edit: also,for manipulating the 2 stacks,you will need to store their stack pointers somewhere .
You can use 2 registers of your choice for that, EBX,ECX for example
make one have the value ESP and the other ESP+L. Every time you will use one stack or the other you will have to update ESP with the appropriate EBX or ECX or wherever you may keep your 2 stack pointers because push and pop will modify ESP and you will want them to modify the version of ESP that is needed and not another one.Also when you finished pop/push you must update EBX/ECX with the values of ESP.

Answer 5

All these answers assume that there is no such thing as operator precedence. Clearly the use of stacks mentioned in the question hints at the correct answer having to do with the calculation making use of operator precedence.

Here is a link that explains what you are trying to achieve. http://epaperpress.com/oper/index.html