Equation (expression) parser with precedence?

by

The shunting yard algorithm is the right tool for this. Wikipedia is really confusing about this, but basically the algorithm works like this:

Say, you want to evaluate 1 + 2 * 3 + 4. Intuitively, you “know” you have to do the 2 * 3 first, but how do you get this result? The key is to realize that when you’re scanning the string from left to right, you will evaluate an operator when the operator that follows it has a lower (or equal to) precedence. In the context of the example, here’s what you want to do:

  1. Look at: 1 + 2, don’t do anything.
  2. Now look at 1 + 2 * 3, still don’t do anything.
  3. Now look at 1 + 2 * 3 + 4, now you know that 2 * 3 has to to be evaluated because the next operator has lower precedence.

How do you implement this?

You want to have two stacks, one for numbers, and another for operators. You push numbers onto the stack all the time. You compare each new operator with the one at the top of the stack, if the one on top of the stack has higher priority, you pop it off the operator stack, pop the operands off the number stack, apply the operator and push the result onto the number stack. Now you repeat the comparison with the top of stack operator.

Coming back to the example, it works like this:

N = [ ]
Ops = [ ]

  • Read 1. N = [1], Ops = [ ]
  • Read +. N = [1], Ops = [+]
  • Read 2. N = [1 2], Ops = [+]
  • Read *. N = [1 2], Ops = [+ *]
  • Read 3. N = [1 2 3], Ops = [+ *]
  • Read +. N = [1 2 3], Ops = [+ *]
    • Pop 3, 2 and execute 2*3, and push result onto N. N = [1 6], Ops = [+]
    • + is left associative, so you want to pop 1, 6 off as well and execute the +. N = [7], Ops = [].
    • Finally push the [+] onto the operator stack. N = [7], Ops = [+].
  • Read 4. N = [7 4]. Ops = [+].
  • You’re run out off input, so you want to empty the stacks now. Upon which you will get the result 11.

There, that’s not so difficult, is it? And it makes no invocations to any grammars or parser generators.

More Related Contents:

  1. How to read values from numbers written as words?
  2. Calculate the sum with minimum usage of numbers
  3. Sum a number with divisors to get another number
  4. Priority scoring algorithm [closed]
  5. What is the optimal algorithm for the game 2048?
  6. How to count the number of set bits in a 32-bit integer?
  7. Algorithm to return all combinations of k elements from n
  8. Reverse the ordering of words in a string
  9. What’s the fastest algorithm for sorting a linked list?
  10. Leap year calculation
  11. Backtracking in A star
  12. What algorithms compute directions from point A to point B on a map?
  13. Algorithm to generate a crossword [closed]
  14. Count number of 1’s in binary representation
  15. Check if one integer is an integer power of another
  16. What is dynamic programming? [closed]
  17. What is the most efficient algorithm to find a straight line that goes through most points?
  18. Find 2 numbers in an unsorted array equal to a given sum
  19. Closest point to a given point
  20. What is amortized analysis of algorithms? [closed]
  21. How modern X86 processors actually compute multiplications?
  22. Random points inside a parallelogram
  23. how do I create a line of arbitrary thickness using Bresenham?
  24. need an algorithm for collapsing netblock ranges into lists of superset ranges
  25. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  26. How do I find the median of numbers in linear time using heaps?
  27. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  28. Finding rectangles in a 2d block grid
  29. Check if array B is a permutation of A
  30. Algorithm to list all unique permutations of numbers contain duplicates

Leave a Comment