foo.bar: Rusty calculator

Last week I wrote about the code challenge foo.bar: Peculiar balance. Today I’ll tease you with another one:

Rusty calculator
================

Lab minion Rusty works for Professor Boolean, a mad scientist. He’s been stuck in this dead-end job crunching numbers all day since 1969. And it’s not even the cool type of number-crunching – all he does is addition and multiplication. To make matters worse, under strict orders from Professor Boolean, the only kind of calculator minions are allowed to touch is the Unix dc utility, which uses reverse Polish notation.

Recall that reverse Polish calculators such as dc push numbers from the input onto a stack. When a binary operator (like “+” or “*”) is encountered, they pop the top two numbers, and then push the result of applying the operator to them.

For example:
2 3 * => 6
4 9 + 2 * 3 + => 13 2 * 3 + => 26 3 + => 29

Each day, Professor Boolean sends the minions some strings representing equations, which take the form of single digits separated by “+” or “*”, without parentheses. To make Rusty’s work easier, write function called answer(str) that takes such a string and returns the lexicographically largest string representing the same equation but in reverse Polish notation.

All numbers in the output must appear in the same order as they did in the input. So, even though “32+” is lexicographically larger than “23+”, the expected answer for “2+3″ is “23+”.

Note that all numbers are single-digit, so no spaces are required in the answer. Further, only the characters [0-9+*] are permitted in the input and output.

The number of digits in the input to answer will not exceed 100.

Test cases
==========

Inputs:
(string) str = “2+3*2″
Output:
(string) “232*+”

Inputs:
(string) str = “2*4*3+9*3+5″
Output:
(string) “243**93*5++”

The solution (in Python) is surprisingly short:

def answer(normal):
    res = ''
    muls = normal.split('+')
    for mul in muls:
        if len(mul) > 1:
            local_mul = mul.split('*')
            res += ''.join(local_mul)
            res += (len(local_mul) - 1) * '*'
        else:
            res += mul 
    res += (len(muls)-1) * '+'    
    return res

That’s definitely NOT the way you should write your code…
Can you figure it out?

Hint: a similar technique was used here

Advertisements
foo.bar: Rusty calculator

4 thoughts on “foo.bar: Rusty calculator

  1. jim fleegens says:

    I think I have a working solution–but it is rejected. 😦

        
        def answer(str):
            countPlus = str.count("+")
            multTerms = map(  lambda s: (s.replace("*", ""))  , str.split("+"))
            addMultSigns = map(  lambda s: s + ("*" * (len(s) - 1))  , multTerms)
            solution = '"' + "".join(addMultSigns) + ("+" * countPlus) + '"'
            return [solution]
    

    Liked by 1 person

    1. Your answer is correct but it’s not returning the result in the correct format – which is why it’s getting rejected.
      Try to replace the last two lines with:

          solution = "".join(addMultSigns) + ("+" * countPlus) 
          return solution
      

      Like

  2. My answer only passes test 4 can I have some feedback?

    def answer(string):
    	if(len(string) 0 and operators_stack[-1] == "*":
    	    output.append(operators_stack.pop())
    	    operators_stack.append("+")
    	else:
    	    output.append(string[x])
    	while len(operators_stack) > 0:
    		output.append(operators_stack.pop())
    	return "".join(output)
    

    Like

    1. Your code can’t run because of a few issues:
      1. output, operators_stack and x are not defined
      2. missing closing parenthesis on the second line
      3. missing comparison operator on the second line before the “0”
      and maybe other issues as well.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s