PDA

View Full Version : Simple calculator "( )" priority needed!



heatblazer
May 9th, 2011, 07:27 PM
Hello. I am programming in C for 4 months / no previous experience/ and I am trying to make a simple calculator using a stack ADT. My problem is that I can`t seem to make the priority of the braces...
like: 10+10+(2*2) to equals to 24 instead of 48... :( Here is my code:
Any advice will be appreciated :)

#include <stdio.h>
#define SIZE 100
int stack[SIZE];
int *sp = stack; /*pointer to the stack*/

/********PROTOTYPES*****************/

void push(int a);
int pop(void);

/******************MAIN*************/
int main(void) {

int i, j;
char ch;
do {
scanf("%d", &i);
push(i);
if ( ch == '+' ) {
push(pop()+pop());
}
if ( ch == '*' ) {
push(pop()*pop());
}
if ( ch == '-' ) {
int temp = pop();
push(pop()-temp);
}
if ( ch == '/' ) {
int temp = pop();
push(pop()/temp);
}
printf("ch is %c \n", ch);

} while( (ch=getchar()) != '=' );

printf("%d is stack\n", stack[0]);
}
/****************************************/

void push(int a) {

*(sp++) = a;
}

int pop(void) {

return *(--sp);
}

simeon87
May 9th, 2011, 08:17 PM
The problem is that you're immediately popping when you encounter a '*' symbol. Let's say we're evaluating 2*(3*4) then you have to process the whole equation first before you can compute the value of the first multiplication. Same for (2*3)*4. You can build a stack-based calculator this way but then you have to use Reverse Polish notation: http://en.wikipedia.org/wiki/Reverse_Polish_notation The proper way of evaluating expressions like these is by building a parse tree, like this one

http://images.immateriel.fr/baw/9780596155971/tagoreillycom20090804oreillyimages316024.png.jpg

and then evaluating each of the nodes to compute the final result.

heatblazer
May 9th, 2011, 08:42 PM
The problem is that you're immediately popping when you encounter a '*' symbol. Let's say we're evaluating 2*(3*4) then you have to process the whole equation first before you can compute the value of the first multiplication. Same for (2*3)*4. You can build a stack-based calculator this way but then you have to use Reverse Polish notation: http://en.wikipedia.org/wiki/Reverse_Polish_notation The proper way of evaluating expressions like these is by building a parse tree, like this one

http://images.immateriel.fr/baw/9780596155971/tagoreillycom20090804oreillyimages316024.png.jpg

and then evaluating each of the nodes to compute the final result.


Nice chart, btw. Well I tested the following:
10+++ it equals to 10+10+10+10... each '+' pushesh s sum of the original pop()... So you propose a linked list for doing this... I`m a newbie yet so a little pseudocode will help :)

simeon87
May 9th, 2011, 09:00 PM
Nice chart, btw. Well I tested the following:
10+++ it equals to 10+10+10+10... each '+' pushesh s sum of the original pop()... So you propose a linked list for doing this... I`m a newbie yet so a little pseudocode will help :)

That's not correct notation because you now have more plus symbols than numbers. But the following examples are in Reverse Polish Notation:

10 10 +
2 3 4 * *

The first is equal to 10 + 10, the second is equal to 2 * (3 * 4). The way it works is:

- Process symbol.
- If it's a number, push it on the stack.
- If it's a + - / *, then pop as needed and compute result. Push that back on the stack.
- Keep going until you're done.

So the above examples would be:

Push(10)
Push(10)
Pop() (gives 10)
Pop() (gives 10)
Push(10 + 10)

and:

2 3 4 * *
Push(2)
Push(3)
Push(4)
Pop() (gives 4)
Pop() (gives 3)
Push(3 * 4)
Pop (gives 12)
Push(2 * 12)

heatblazer
May 9th, 2011, 09:08 PM
That's not correct notation because you now have more plus symbols than numbers. But the following examples are in Reverse Polish Notation:

10 10 +
2 3 4 * *

The first is equal to 10 + 10, the second is equal to 2 * (3 * 4). The way it works is:

- Process symbol.
- If it's a number, push it on the stack.
- If it's a + - / *, then pop as needed and compute result. Push that back on the stack.
- Keep going until you're done.

So the above examples would be:

Push(10)
Push(10)
Pop() (gives 10)
Pop() (gives 10)
Push(10 + 10)

and:

2 3 4 * *
Push(2)
Push(3)
Push(4)
Pop() (gives 4)
Pop() (gives 3)
Push(3 * 4)
Pop (gives 12)
Push(2 * 12)

I was thinking of a string separation usign atoi to check if it is a number then push it to the stack and after encountering a symbol like +,-,* or / to pop then push back dependantly of the next atoi string...
Or... I can have 2 stacks - integer and symbol in the int I`ll store numbers, in symbol I`ll store operators then pop as it follows:

intstaack 1, 2, 3

symbolstack +, *, -;

then I can add () to make a fake priority by pushing later symbols... :confused: too nerdy

simeon87
May 9th, 2011, 09:28 PM
I was thinking of a string separation usign atoi to check if it is a number then push it to the stack and after encountering a symbol like +,-,* or / to pop then push back dependantly of the next atoi string...
Or... I can have 2 stacks - integer and symbol in the int I`ll store numbers, in symbol I`ll store operators then pop as it follows:

intstaack 1, 2, 3

symbolstack +, *, -;

then I can add () to make a fake priority by pushing later symbols... :confused: too nerdy

There are many ways to implement a parser. If you wish to use two stacks that's fine, it's just that Reverse Polish Notation doesn't require more than one stack.

schauerlich
May 9th, 2011, 10:28 PM
One simple thing you could do to both keep your infix notation and still be able to evaluate expressions easily and using a stack is to convert the infix expression to reverse polish notation, and then evaluate the resulting expression. You can use Dijkstra's Shunting Yard Algorithm for this. There's a bunch of information here (http://ubuntuforums.org/showthread.php?t=1441700), including a lot of examples.