Writing a simple equation parser

by

You can use Shunting yard algorithm or Reverse Polish Notation, both of them are using stacks to handle this, wiki said it better than me.

From wiki,

While there are tokens to be read:

    Read a token.
    If the token is a number, then add it to the output queue.
    If the token is a function token, then push it onto the stack.
    If the token is a function argument separator (e.g., a comma):

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

    If the token is an operator, o1, then:

        while there is an operator token, o2, at the top of the stack, and

                either o1 is left-associative and its precedence is less than or equal to that of o2,
                or o1 is right-associative and its precedence is less than that of o2,

            pop o2 off the stack, onto the output queue;

        push o1 onto the stack.

    If the token is a left parenthesis, then push it onto the stack.
    If the token is a right parenthesis:

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
        Pop the left parenthesis from the stack, but not onto the output queue.
        If the token at the top of the stack is a function token, pop it onto the output queue.
        If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

When there are no more tokens to read:

    While there are still operator tokens in the stack:

        If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
        Pop the operator onto the output queue.

Exit.

More Related Contents:

  1. How to find number of words in a phrase with spaces removed by checking v. dictionary
  2. What is the most effective way for float and double comparison?
  3. How to parse a string to an int in C++?
  4. Fast bignum square computation
  5. Detecting endianness programmatically in a C++ program
  6. Algorithm to convert RGB to HSV and HSV to RGB in range 0-255 for both
  7. Parse (split) a string in C++ using string delimiter (standard C++)
  8. What is the efficient way to count set bits at a position or lower?
  9. Fast exact bigint factorial
  10. Generating combinations in c++
  11. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  12. Lock-free Progress Guarantees in a circular buffer queue
  13. Finding duplicates in O(n) time and O(1) space
  14. Cross-platform way to get line number of an INI file where given option was found
  15. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  16. Emulate “double” using 2 “float”s
  17. Need for predictable random generator
  18. Determining if a number is prime
  19. How to add two numbers without using ++ or + or another arithmetic operator
  20. Are there any better methods to do permutation of string?
  21. Iterative DFS vs Recursive DFS and different elements order
  22. C++ Remove punctuation from String
  23. Searching in a sorted and rotated array
  24. `std::list::sort()` – why the sudden switch to top-down strategy?
  25. How can I sort an STL map by value?
  26. C++ Templates Angle Brackets Pitfall – What is the C++11 fix?
  27. What is the safe way to fill multidimensional array using std::fill?
  28. Is it possible to implement lock free map in C++
  29. Calculate mean and standard deviation from a vector of samples in C++ using Boost
  30. Checking if all elements of a vector are equal in C++

Leave a Comment