Short description of the algorithm:
  1. give each operator/operand a priority based on it's depth and on a base priority each has.
  2. take the biggest priority operand and the 2 operands adjacent to it
  3. evaluate the 3 elements extracted at step 2 and put in the array at the place where they were the result of the calculation and the results's priority is decreased by a depth_bonus because it's paranthesis have disappeared.
  4. repeat step 2 until the array has just one element(which is the result of the evaluation)

On the surface, it looks like this algorithm should work, however, it seems like you are doing more work than is necessary, and the algorithm reduces basically to an infix-to-postfix conversion combined to a postfix calculation but with a larger big o complexity.

Since you are able to parse and calculate postfix with a single pass through the data and a stack, and convert from infix to postfix with a single pass and stack, I am not certain what this buys you.

As far as your implementation, for educational purposes, go crazy. On my initial scan, I would have concerns with the element selection routine, but it appears that it should work. For performance, I would be concerned with the repeated sorts.

If this is not for educational reasons, then I would seriously consider looking at the algorithms listed above, a parse tree, and a postorder traversal of that tree, as those are probably able to be implemented with less code and less complexity.

--MidLifeXis

In reply to Re: a timid approach to parsing arithmetic expressions in perl by MidLifeXis
in thread a timid approach to parsing arithmetic expressions in perl by spx2

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.