Stacks and arithmetic expressions

Hello,

I recently came upon a problem. In the Uni I am in, we received an assignment to write a function that can evaluate an arithmetic expression. First thought: Binary Tree, but the first detail of the assignment: Trees are not allowed. So the hint was to use a stack..

We never learned anything about stacks or queues or any sort of that, so Im kind of feeling helpless. I searched google/yahoo and came upon only one 'good' article which was in wikipedia. http://en.wikipedia.org/wiki/Stack_%28data_structure%29

So I am asking here for any help people might offer. What are stacks really? How do the push, pop functions work? DO I have to convert the arithmetic expression into Postfix form first? (The symbols allowed are +-/*% and parantheses, so thank god no variables or that sort, but the numbers can be infinitely long). Are stacks really the only way to solve this? [excluding binary trees]

Any help would be greatly appreciated!

There is a thin line between the definition of "only" and "most suitable" - everything can be solve "in a different way" if you try hard enough, but there are really "only" two reasonable solutions to this type of problem, one is a stack approach, and the other being binary tree.

--
Mats

> What are stacks really?
Just a data structure.
A bit like a queue, with the restriction that you can only use one end.

> How do the push, pop functions work?
Any way you like.
How you implement a stack (array, linked list) doesn't matter so long as you implement the idea of 'push' and 'pop' according to normal stack semantics.

> DO I have to convert the arithmetic expression into Postfix form first?
Probably not, though it certainly makes any evaluation a hell of a lot easier if you do.

I think you need this to turn infix into postfix
http://en.wikipedia.org/wiki/Shunting_yard_algorithm


> We never learned anything about stacks or queues or any sort of that
You're missing a hell of a lot then. Programming is a lot more than learning the keywords and where to put the curly braces.
http://www.nist.gov/dads/

Quote:

---

How you implement a stack (array, linked list) doesn't matter so long as you implement the idea of 'push' and 'pop' according to normal stack semantics.

---

Thank you for the help, would you by any chance have a link or example of how do I implement a stack? Since the numbers can be infinitely long, I believe I need to implement a stack using a linked list.

Also, I keep on seeing this word "token"., "tokenizer". What is that?

In reverse:
A token is roughly the same as a "symbol", e.g. a number or an operator.

You don't necessarily need to use a linked list just because your numbers are arbitrarily large [do you have a math library to perform the calculation, or will you have to write the basic math too?]

For example:

Code:

---

struct elem
{
    union {
      Data *data;
      opertype oper;
    } operData;
    bool isData;
};

struct elem stack[STACKSIZE];

---

would give you a stack that contains either an arbitrarily large operand or some operator.

As for "how to implement in a linked list", it would be fairly easy - just think about it for a few minutes - perhaps with a piece of paper to draw what's on the stack at any given time and add/remove some elements onto/from the stack.

--
Mats

A stack is basicly a bunch of memory addresses for you data.
it works on a FOLO operation' first on last off .
the opisit to a stack is a heap.
I hope this helps a little this is what I picked up from class the other day at uni :)
when using pointers you only refer to a address in the "stack" u need to use the * to "derefrence" the address which will give you the content at that memory location in your stack. LOL wow I think I have been learning

I have to write from scratch. What I meant by infinite large is that the number of numbers can be infinitely large. So I can be adding or subtracting, etc. thousands of numbers. Something like 5+3/2(6-2)*34+5+321/2(11-2)*(4+5+8/2(9-3))*4 and goes on and on infinitely long.

So a stack is basically a structure type thing? Was the union in your example necessary?

The union is not necessary - it just reduces the overhead of the stack. Particularly, if you have only integer or double numbers, you can easily just stick the number and the operand, and have a bool to distinguish them.

A stack, in itself, is like a stack of plates in your kitchen cupboard - each plate would have a "value" or "an operator", and you can take a plate at the time - but you are not allowed to lift 5 plates off, pull out the blue plate underneath and just drop the give plates back down again - that's not a stack then!

So push() is the operation of taking a plate from the draining board and into the cupboard. The pop() operation takes a plate off the stack.

You can have a "stack" of just integers [but that wouldn't work for holding operators and numbers - because you need something to say "this is an operator" and you probably want to support ALL valid integer values].

You can have a stack of complicated data structures.

Your stack can be implemented as an array or as a linked list, as two of the more obvious solutions. There are probably other ways to implement the stack.

In your case, if it's REALLY infinite number of operands and operators, then you probably do need a linked list, rather than a fixed size array. An alternative solution is a dynamically allocated array - so you start out by allocating a (relatively) small amount of space, then use re-alloc to grow it (e.g double the size) if you run out of stack.

--
Mats

A stack is not defined by its structure, so much as it is defined by its operations. Basically, anything where you can only remove(pop) the most recently added(pushed) object is a stack. The shunting yard algorithm, which appears to be what you are looking for, is a good example of stack use.




If you understand how to construct a tree, then it is surprising for you to not have been taught to construct a stack. Following is basically a minimalist implementation of a stack, with some testing code.

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// There are basically two good ways to implement a stack,
// One is to use a linked list, in which you add and remove elements from the head of the list.
// The other (generally better) manner is to use a resizable array.

#define STACKSIZE 500

typedef struct {
        int data[STACKSIZE];
        unsigned int top;
} intstack;

// Pops the top element of the intstack into result.
// Returns 1 on success, 0 on failure.
// This should only fail if the stack is empty.
int intstack_pop (intstack * pop_me, int * result) {
        if (pop_me->top == 0) return 0;

        --pop_me->top;
        *result = pop_me->data[pop_me->top];

        return 1;
}

// Pushes push_me onto intstack target.
// Returns 1 on success, 0 on failure
int intstack_push (intstack * target, int push_me) {
        if (target->top == STACKSIZE) return 0;

        target->data[target->top] = push_me;
        ++target->top;

        return 1;
}

int main (void) {
        intstack my_intstack;
        int i;

        my_intstack.top = 0;

        printf ("Pushing 1\n");
        assert(intstack_push (&my_intstack, 1));

        printf ("Pushing 2\n");
        assert(intstack_push (&my_intstack, 2));

        assert(intstack_pop (&my_intstack, &i));
        printf ("Popping &#37;d\n", i);

        for (i = 5; i < 26; ++i) {
                printf ("Pushing %d\n", i);
                assert(intstack_push(&my_intstack, i));
        }

        while (intstack_pop(&my_intstack, &i)) {
                printf ("Popping %d\n", i);
        }

        return 0;
}

---

Quote:

---

Originally Posted by +Azazel+

Also, I keep on seeing this word "token"., "tokenizer". What is that?

---

A token is a specific grammatical unit of a language. In the case of basic arithmetic expressions, the tokens are numbers, operators, and parentheses. To tokenize a string means to break it into individual tokens according to the grammar of the language.

A specific incarnation of a token is called a lexeme. For instance, the lexical occurrence of "12345" is a token of type "number," and its lexeme is the value 12345.

Comparing with English, the word "acorn" is a token of type "noun" and the lexeme is the word "acorn" itself.

Most language parsers are two-stage, with a tokenizer at the front which breaks the raw input into tokens. The tokenizer feeds the tokens/lexemes into the parser itself.

Hello again,

While working on the assignment, it turned out that its actually the numbers that can be infinite not the length of the chain. So I might be multiplying digits that are larger than what a variable can hold. Ive been looking through the Karatsuba method and Schönhage-Strassen algorithm for multiplication but I was unable to find any algorithms like that in C. Perhaps someone knows of any algorithms for multiplication, division, addition, or subtraction?

Second question: Is there a way to access the L1 and L2 cache and use a tiny bit of it for an operation? So as to speed up the program?

Thank you!

Quote:

---

Originally Posted by +Azazel+

Hello again,

While working on the assignment, it turned out that its actually the numbers that can be infinite not the length of the chain. So I might be multiplying digits that are larger than what a variable can hold. Ive been looking through the Karatsuba method and Schönhage-Strassen algorithm for multiplication but I was unable to find any algorithms like that in C. Perhaps someone knows of any algorithms for multiplication, division, addition, or subtraction?

Second question: Is there a way to access the L1 and L2 cache and use a tiny bit of it for an operation? So as to speed up the program?

Thank you!

---

This is a good resource - wouldn't bother about efficiency at this time - just make it work with one of the simple methods described:
http://en.wikipedia.org/wiki/Multiplication_algorithm

A quick google for other math operations should be fairly easy - and add/subtract are really easy to do with string operations. Just need a loop and a carry to the next value. Normalizing the values [making them equal length] will make the rest of the math simpler.

Divide will certainly be hardest - but as long as you are happy to be inefficient, I'd say that it's fine.

As to using the cache - the processor will automatically use the cache when you are accessign data that you have recently used - it loads ALL data that you use into the L1 cache, and if you re-use it before it's been shuffled out of the L1 cache, it will be used from there. It is actually more of a problem to AVOID using the cache when working on really large problems - those where you KNOW that the data will not be re-used, and thus makes no sense to store in the cache. But I doubt you'll have that particular problem here, as caches on modern processors are severa hundred kilobytes, even into the megabytes for the latest models.

--
Mats