Regexp issue involving reverse polish calculator

2019-07-16 07:05发布

I'm trying to use a regular expression to solve a reverse polish calculator problem, but I'm having issues with converting the mathematical expressions into conventional form.

I wrote:

puts '35 29 1 - 5 + *'.gsub(/(\d*) (\d*) (\W)/, '(\1\3\2)')

which prints:

35 (29-1)(+5) *

expected

(35*((29-1)+5)) 

but I'm getting a different result. What am I doing wrong?

1条回答
祖国的老花朵
2楼-- · 2019-07-16 07:47

I'm assuming you meant you tried

puts '35 29 1 - 5 + *'.gsub(/(\d*) (\d*) (\W)/, '(\1\3\2)')
                    ^           ^

Anyway, you have to use the quantifier + instead of *, since otherwise you will match an empty string for \d* as one of your captures, hence the (+5):

/(\d+) (\d+) (\W)/

I would further extend/constrain the expression to something like:

/([\d+*\/()-]+)\s+([\d+*\/()-]+)\s+([+*\/-])/
 |             |  |             |   |
 |             |  |             |   Valid operators, +, -, *, and /.
 |             |  |             |   
 |             |  |             Whitespace.
 |             |  |                 
 |             |  Arbitrary atom, e.g. "35", "(29-1)", "((29-1)+5)".
 |             |                    
 |             Whitepsace.                  
 |
 Arbitrary atom, e.g. "35", "(29-1)", "((29-1)+5)".

...and instead of using gsub, use sub in a while loop that quits when it detects that no more substitutions can be made. This is very important because otherwise, you will violate the order of operations. For example, take a look at this Rubular demo. You can see that by using gsub, you might potentially replace the second triad of atoms, "5 + *", when really a second iteration should substitute an "earlier" triad after substituting the first triad!

WARNING: The - (minus) character must appear first or last in a character class, since otherwise it will specify a range! (Thanks to @JoshuaCheek.)

查看更多
登录 后发表回答