Read string for arithmetic operation

[Thomas Kreuzer]

Hello everyone,

I have a question regarding how to interpret a string.

Basically I want to write a little calculator, I will type something
like "12+69*12-44/2" and then want my program to compute it into the
result :)

I experimented a bit with strtok and the like, but I think I am not sure
how I should approach this problem. The problem being the priorities of
the operators of course.

Should I split the string? Right now I just put all numbers in a list,
so I would get:
12->69->12->44->2
Now I could make the same for the signs like +->*->-->/ and try to sort
things out and so on, I am really not sure.

Anyone got a hint for me how to do this?
I am thankful for any idea.

Thomas

[websnarf]

Thomas Kreuzer wrote:

Hello everyone,
I have a question regarding how to interpret a string.

Basically I want to write a little calculator, I will type something
like "12+69*12-44/2" and then want my program to compute it into the
result :)

I experimented a bit with strtok and the like, but I think I am not sure
how I should approach this problem.

strtok is a problematic function. I would recommend you do it via the
strcspn(p) functions.

[...] The problem being the priorities of
the operators of course.

Should I split the string? Right now I just put all numbers in a list,
so I would get:
12->69->12->44->2
Now I could make the same for the signs like +->*->-->/ and try to sort
things out and so on, I am really not sure.

Anyone got a hint for me how to do this?

The key is to to scan the expression, and first of all distinguish
between subtraction and negation. Then what you do is you find the
first operator with the *least* precidence. So in your case, its the
"+" after the "12". Then you recursively calculate each parameter for
the operation, in this case "12" and "69*12-44/2", which will end up as
12 and the other as 806. Then switch on the operator "+" to an
addition code snippet, which would add the two results to get 806 + 12
= 818. Then just return this final result.

The tricky part is basically keeping track of parenthesis levels and
detecting the difference between negation and subtraction. Negation
has higher precidence than subtraction, so this actually makes a big
deal. So you'll know things are sort of working when you can parse:

1-2----(--3-4)-5

correctly.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[goose]

Thomas Kreuzer wrote:

Hello everyone,

I have a question regarding how to interpret a string.

Basically I want to write a little calculator, I will type something
like "12+69*12-44/2" and then want my program to compute it into the
result :)

I experimented a bit with strtok and the like, but I think I am not sure
how I should approach this problem. The problem being the priorities of
the operators of course.

Should I split the string? Right now I just put all numbers in a list,
so I would get:
12->69->12->44->2
Now I could make the same for the signs like +->*->-->/ and try to sort
things out and so on, I am really not sure.

Anyone got a hint for me how to do this?

assuming that operands is the list of operands and
operators is the list of operators:

12+69*12-44/2
=[12 69 12 44 2] (array of operands)
=[+ * - /] (array of operators)
while (operators has at least one operator) {
i = first position of * or / in operators
if no * or / found, then i = first operator
apply operators[i] on operands[i] and operands[i+1]
store result in operands[i]
remove operands[i+1]
remove operators[i]
}

Try changing the steps to include correct parsing
of nested braces.

goose,

[Thomas Kreuzer]

The question is what is faster, or "better".
Is the list approach useful? Or should I try to make it recursively like
it was suggested? Most of the time recursions are slower then
iterations, but with lists I have to go through them a lot of times etc.

My main goal will not be just a simple calculator but I want actually
matrix operations implemented and this is then my underlying function to
compute all arithmetic expressions. So it should be as fast as possible
with my abilities :)

A compile must have a similar algorithm, how do they parse the strings?

Thanks in advance,
Thomas

[CBFalconer]

Thomas Kreuzer wrote:

>
The question is what is faster, or "better". Is the list approach
useful? Or should I try to make it recursively like it was
suggested? Most of the time recursions are slower then iterations,
but with lists I have to go through them a lot of times etc.

My main goal will not be just a simple calculator but I want
actually matrix operations implemented and this is then my
underlying function to compute all arithmetic expressions. So it
should be as fast as possible with my abilities :)

A compile must have a similar algorithm, how do they parse the
strings?

You neglected to quote whatever you are replying to, and the result
makes no sense. Always ensure your articles stand by themselves.

I suspect you are trying to convert a text string into an
arithmetic expression. This requires a lexical analyser, probably
best followed by conversion to reverse Polish notation (look that
up), together with suitable error detection.

--
Chuck F (cb********@yahoo.com) (cb********@maineline.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.netUSE maineline address!