Read string for arithmetic operation

Discussion in 'C Programming' started by Thomas Kreuzer, Aug 3, 2006.

  1. 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
     
    Thomas Kreuzer, Aug 3, 2006
    #1
    1. Advertising

  2. Thomas Kreuzer

    Guest

    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/
     
    , Aug 3, 2006
    #2
    1. Advertising

  3. Thomas Kreuzer

    goose Guest

    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 on operands and operands[i+1]
    store result in operands
    remove operands[i+1]
    remove operators
    }

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

    goose,
     
    goose, Aug 4, 2006
    #3
  4. 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
     
    Thomas Kreuzer, Aug 4, 2006
    #4
  5. Thomas Kreuzer

    CBFalconer Guest

    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 () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE maineline address!
     
    CBFalconer, Aug 4, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. joshc
    Replies:
    5
    Views:
    575
    Keith Thompson
    Mar 31, 2005
  2. Mehta Shailendrakumar

    Arithmetic shift operation in C

    Mehta Shailendrakumar, Jun 15, 2005, in forum: C Programming
    Replies:
    43
    Views:
    2,488
    Richard Bos
    Jun 21, 2005
  3. david ullua
    Replies:
    13
    Views:
    675
  4. Buzz Lightyear
    Replies:
    10
    Views:
    1,137
    Alexander Bartolich
    Aug 12, 2009
  5. Manoj Chourasia

    Arithmetic operation bug

    Manoj Chourasia, Jul 24, 2009, in forum: Ruby
    Replies:
    3
    Views:
    107
    Stefano Crocco
    Jul 24, 2009
Loading...

Share This Page