Parsing math notations (Easy)

This is a discussion on Parsing math notations (Easy) within the C Programming forums, part of the General Programming Boards category; Hi. Im trying to write a program that can read Strings such as: 1+2*3+4 36-89*3 And return the answer using ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    1

    Question Parsing math notations (Easy)

    Hi.

    Im trying to write a program that can read Strings such as:

    1+2*3+4
    36-89*3

    And return the answer using the correct orders of operation.

    Im pretty sure I need to implement some sort of parse tree, but I cant remember how to do that.

    Is there a function in the standard library that can do this for me? Or any example source code for one?

    thanks!

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Read Wikipedia and search this forum, for Reverse Polish Notation.

    You use 2 stacks, and push and pop numbers and operators on and off. Pretty slick stuff.

  3. #3
    Why bbebfe is not bbebfe? bbebfe's Avatar
    Join Date
    Nov 2008
    Location
    Earth
    Posts
    27
    Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
    Do you know why bbebfe is NOT bbebfe?

  4. #4
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
    Overkill in this case

  5. #5
    Why bbebfe is not bbebfe? bbebfe's Avatar
    Join Date
    Nov 2008
    Location
    Earth
    Posts
    27

    Talking

    Quote Originally Posted by zacs7 View Post
    > Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
    Overkill in this case
    Haha, just a little.
    Do you know why bbebfe is NOT bbebfe?

  6. #6
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Ritchie & Kernighan explain how to evaluate an equation in reverse polish notation, but if you want to read in impix notation (like example above) you will need to use a shunting yard algotithm which I am in the process of writing, need help though. It is easier to work only in reverse polish, e.g. your first example (1+2*3+4) would become something like: 2 3 * 1 + 4 +
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,636
    A little off topic, but I was puzzled by the term "impix notation". Is that really an alternative name for infix notation?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > Is that really an alternative name for infix notation?
    No. Well no-one I've spoken to has heard of it. Including a maths professor and a CS professor.

    My guess is a "communication" error on their side :-)

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quote Originally Posted by Adak View Post
    Read Wikipedia and search this forum, for Reverse Polish Notation.

    You use 2 stacks, and push and pop numbers and operators on and off. Pretty slick stuff.
    Did he ask for reverse polish notation?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,636
    Quote Originally Posted by master5001
    Did he ask for reverse polish notation?
    I am sure that you are aware that converting expressions from infix notation into reverse polish notation as an intermediate step is one way to evaluate expressions in infix notation.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Getting into mathmatical analysis can get tricky when dealing with postfix and prefix(Lukasiewicz) methods of the expressions as order of the values is very important, take for instance subtraction and division.

    1+2*3+4 ==> 1 2 3 * + 4 + postfix parenthesis are not necesary
    36-89*3 ==> 36 89 3 * - postfix


    So if you can just rearange the input accordingly then performing the postfix or prefix methods via a function call would be much easier.

  12. #12
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Forgot to mention that such work makes use of stack behaviour and complicated mathematics are solved this way. "Algorithms in C" addresses this very thing which I happen to be studying atm.

  13. #13
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Quote Originally Posted by laserlight View Post
    A little off topic, but I was puzzled by the term "impix notation". Is that really an alternative name for infix notation?
    Sorry, typo. Turns out that went w/ thinking that ASCII was ANCII. Mabye when I first saw the word, I read it too quickly.
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Math
    By knightjp in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 04-01-2009, 05:36 PM
  2. Math Function Input
    By swanley007 in forum C++ Programming
    Replies: 2
    Last Post: 02-15-2006, 06:29 PM
  3. how to use operator+() in this code?
    By barlas in forum C++ Programming
    Replies: 10
    Last Post: 07-09-2005, 07:22 PM
  4. Easy Math Question
    By MethodMan in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-23-2003, 10:00 AM
  5. I hate string parsing with a passion
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 03-19-2002, 06:30 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21