3

I'm pretty stuck in finding a proper solution for a given problem, been looking for some ideas over the internet. Wasn't be able to find any.

Problem is: writing a program that takes from the standard input an expression without left parentheses and prints the equivalent infix expression with the parentheses inserted.

Given expression: 1 + 2) * 3 - 4)* 5 - 6)))
Output: ((1 + 2) * ((3 - 4) * (5 - 6)))

What can be the best approach to solve this problem?

6
  • 3
    How do you know it's not supposed to be 1 + ((2) * 3 - ((4)* 5 - (6)))?
    – lc.
    Sep 28, 2013 at 2:57
  • Do you just want to put a left parenthesis after the following operand from the previous right parenthesis?
    – jab
    Sep 28, 2013 at 2:58
  • @lc, cause the output format has been given as an answer.
    – mehdix_
    Sep 28, 2013 at 3:01
  • 2
    @mehdix_ This is not about the format at all, it's a completely different interpretation. As it stands, this question is incomplete and not answerable.
    – us2012
    Sep 28, 2013 at 3:03
  • @jab, would've been easy that way! but I don' think that'll work. The algorithm should be able to parse the input, evaluate the missing parenthesis pairs.
    – mehdix_
    Sep 28, 2013 at 3:10

1 Answer 1

12

I think that the goal is assuming that you only parenthesize expressions, not lone numbers.

So you'll want to grab each token and toss them on a stack

2
+
1

grab the next token, which is ) now take the top three of the stack and sandwich it between those parens ( 1 + 2 ), put it back on the stack as one expression.

next push the stack looks like this

4
-
3
*
(1 + 2)

pull out the top three and put it back on the stack parenthesized (3-4) * (1+2)

and again

6
-
5
*
(3-4)
*
(1+2)

we hit another paren and grab the top 3 from the stack again, parenthesize and push back

(5-6)
*
(3-4)
*
(1+2)

We grab another paren, grab the top 3 from the stack again, parenthesize and push back

((3-4)*(5-6))
*
(1+2)

and again...

((1 + 2) * ((3 - 4) * (5 - 6)))

no more input, so this is our answer

2
  • wonderful, that's the way through. you were a great help @agoaj
    – mehdix_
    Sep 28, 2013 at 21:59
  • there is a bug because the final parentheses is not balanced.
    – TheM00s3
    May 28, 2015 at 20:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.