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?

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
mehdix_
  • 479
  • 1
  • 7
  • 20
  • 3
    How do you know it's not supposed to be `1 + ((2) * 3 - ((4)* 5 - (6)))`? – lc. Sep 28 '13 at 02:57
  • Do you just want to put a left parenthesis after the following operand from the previous right parenthesis? – jab Sep 28 '13 at 02:58
  • @lc, cause the output format has been given as an answer. – mehdix_ Sep 28 '13 at 03: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 '13 at 03: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 '13 at 03:10
  • @us2012, unfortunately this is coming from a book which is now being used by so many computer science major. – mehdix_ Sep 28 '13 at 03:11

1 Answers1

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

agoaj
  • 369
  • 6
  • 13