Building a calculator

I have been trying to build a calculator, and i got to a point where i have 2 arrays: char array that contains the math operation signs and a int array for the numbers. And I need to do the calculation.
for example, the 2 arrays are:

Code:

int Nums[]={12, 8, 7, 3};
char Signs[]={+, /, (, -, );

so it is supposed to get this:
12+8/(7-3)
which is 5.

the terms are:
- the program should know what comes after what.(because there is only 1 possible option at a time).
- there are only 6 signs: +, -, /, *, (, ).
- If the user doesnt provide brackets around divide or multiple operation (or any other operation) the program should calculate from left to right, and not in order of arithmetic operations.
- The user should be able to insert brackets into other ones, or in the begining.


I have already wrote the code for the 4 arithmetic operations, but when the brackets came in i got lost. I think i can think of something to suite them, but it's really long and inefficient code.
Can someone give me an idea how to do this?

Thanks in advance.

Code:

12+8/(7-3)
which is 5.

Or 12 + (8/(7-3)) = 12 + 8 / 4 = 12 + 2 = 14?

For parenthesis, you need to use a stack.

--
Mats

Originally Posted by matsp

Code:

12+8/(7-3)
which is 5.

Or 12 + (8/(7-3)) = 12 + 8 / 4 = 12 + 2 = 14?

For parenthesis, you need to use a stack.

--
Mats

I dont understand, what are you saying? I have already said that If the user doesnt provide parenthesis the program should calculate from left to right, and not in order of arithmetic operations, so why would it be 12 + (8/(7-3)) ? there are only 2 parenthesis in the char array.

Ok, fair enough, 12 + 8 / 4 is 5, yes.

--
Mats

Now that we've got that cleared up, you still need a stack. IOW: every time you see a (, you need to "start over" and work until you see a ). Then return back to the "original problem" with the whole (expression) turned into just the number.

Yes, exactly - whenever you see a parenthesis, you need to calculate the content of the parenthesis and once that's finished, you can continue with the previous calculation.

--
Mats

Originally Posted by matsp

Yes, exactly - whenever you see a parenthesis, you need to calculate the content of the parenthesis and once that's finished, you can continue with the previous calculation.

--
Mats

There is another approach as I remember: 2-pass calculator

1st pass parses the string reverting the expression into hungarian notation (if I remembre correctly the name) using rather simple stack procedure
like
12+8/(7-3)
to

12,8,7,3,-,/,+

And On the second pass calculates the resulting expression using another stack
push 12
push 8
push 7
push 3
- : pop, pop, apply -
push 4
/: pop, pop, apply /
push 2
+: pop, pop, apply +
push 14
pop: return 14

1st pass parses the string reverting the expression into hungarian notation (if I remembre correctly the name)

No, Polish (prefix) or reverse Polish (postfix) notation. Hungarian notation refers to the coding style.

This two pass algorithm is known as the Shunting Yard algorithm.

Originally Posted by laserlight

No, Polish (prefix) or reverse Polish (postfix) notation. Hungarian notation refers to the coding style.

This two pass algorithm is known as the Shunting Yard algorithm.

Sorry, I read the book about 15 years ago and havn't used this notation since there...

Originally Posted by vart

There is another approach as I remember: 2-pass calculator

1st pass parses the string reverting the expression into hungarian notation (if I remembre correctly the name) using rather simple stack procedure
like
12+8/(7-3)
to

12,8,7,3,-,/,+

And On the second pass calculates the resulting expression using another stack
push 12
push 8
push 7
push 3
- : pop, pop, apply -
push 4
/: pop, pop, apply /
push 2
+: pop, pop, apply +
push 14
pop: return 14

Sure, that's another way to implement the function [although we should actually divide 20 by 4 acording to the original post - I'm glad I wasn't the only one assuming proper priorities here.

--
Mats

Originally Posted by tabstop

Now that we've got that cleared up, you still need a stack. IOW: every time you see a (, you need to "start over" and work until you see a ). Then return back to the "original problem" with the whole (expression) turned into just the number.

Yes I was just thinking about it. using a simple recursion - every time there is a '(' the function call to itself and keep calculating, until it gets a ')' and than returns. But I had some problems implementing it - assuming there is a '+' sign, how can the function know weather there is an arithmetic operation after that or a parenthesis, during one run of the loop? I hope i have explained myself well enough, and if not, can you give me a general direction on how to do it?

vart, thanks for the answer. So ok, assuming there should be a proper priorities, accoring to your way, what will you do if the input is something like this:
16/10-((8*2)-1)
you cant pop them one by one from right to left as you did with the first. The function has to know what operation to do first, and this is exactly the problem Im trying to figure out.

Yes I was just thinking about it. using a simple recursion - every time there is a '(' the function call to itself and keep calculating, until it gets a ')' and than returns.

Recursion uses a stack too, but this time the entire environmental context of the function is saved in the stack, which can be unnecessarily expensive. If you use your own stack, you can decide exactly what you want to save.

But I had some problems implementing it - assuming there is a '+' sign, how can the function know weather there is an arithmetic operation after that or a parenthesis, during one run of the loop? I hope i have explained myself well enough, and if not, can you give me a general direction on how to do it?

I suggest that you search the Web concerning the shunting yard algorithm.

It is also probable that you will find a lot of implementations also with a good search. Because the nature of the problem is such that so many before you have already solved, the best you can gain from it's solution is probably someone elses solution.

Ok guys, after long hours of searching and researching the web (specifically wiki) trying to figure out what is shunting yard algorithm, what is polish notation (and what is notation at all), and how all this works - I finally did it! I managed to get how it works, and i also had to refresh my knowledge about stack and queues because I have never really had to work with them.
so thank you all for the help, you are great.


Man, polish notation..... those polish are genius