Ex_1_3_09.md

title	Algorithm4 Java Solution 1.3.09
date	2019-07-04 05:47:10 +0800
draft	false
tags	JAVA
categories	TECH archives

1.3.09

Problem:

Write a program that takes from standard input an expression without left parentheses and prints the equivalent infix expression with the parentheses inserted. For example, given the input:

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

output:

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

Solution：

we are about to use two stacks:

first stack is used to save expression string, the other stack is used to save operators(+-*/).

example:

expr_stack: push 1, 2
op_stack: push +
then read ")"
we pop two operands from expr_stack: 1 and 2
then, pop operator + from op_stack
( 1 + 2 ) forms a new operands, then push back to expr_stack
...
and so on....

Reference：