1+ /*********************************************************************************
2+ * (Convert infix to postfix) Write a method that converts an infix expression *
3+ * into a postfix expression using the following header: *
4+ * *
5+ * public static String infixToPostfix(String expression) *
6+ * For example, the method should convert the infix expression (1 + 2) * 3 to *
7+ * 1 2 + 3 * and 2 * (1 + 3) to 2 1 3 + *. *
8+ *********************************************************************************/
9+ import java .util .*;
10+
11+ public class Exercise_20_16 {
12+ public static void main (String []args ) {
13+ // Test method infixToPostfix and display result
14+ System .out .println ("Infix Expression Postfix Expression" );
15+ System .out .println (" (1 + 2) * 3 "
16+ +infixToPostfix ("(1 + 2) * 3" ));
17+ System .out .println (" 2 * (1 + 3) "
18+ +infixToPostfix ("2 * (1 + 3)" ));
19+ }
20+
21+ /** Method converts an infix expression into a postfix expression */
22+ public static String infixToPostfix (String expression ) {
23+ // Create a Linked list to store the result
24+ LinkedList <String >operatorList =new LinkedList <>();
25+
26+ // Create a Linked list to store operands
27+ LinkedList <String >resultList =new LinkedList <>();
28+
29+ // Create a stack to store '('
30+ Stack <Character >stack =new Stack <>();
31+
32+ // Insert blanks around (, ), +, -, /, and *
33+ expression =insertBlanks (expression );
34+
35+ // Extract operands and operators
36+ String []tokens =expression .split (" " );
37+
38+ // Scan tokens
39+ for (String token :tokens ) {
40+ if (token .length () ==0 )// Blank space
41+ continue ;// Back to the while loop to extract the next token
42+ else if (token .charAt (0 ) =='(' )// Push '(' onto the stack
43+ stack .push (token .charAt (0 ));
44+ else if (!stack .isEmpty () &&stack .peek () =='(' &&
45+ token .charAt (0 ) !=')' ) {
46+ // Place operators within "( )" and the
47+ // front to the front of the operatorList
48+ if (Character .isDigit (token .charAt (0 )))
49+ resultList .addLast (token );
50+ else if (token .charAt (0 ) =='+' ||token .charAt (0 ) =='-' ||
51+ token .charAt (0 ) =='*' ||token .charAt (0 ) =='/' )
52+ operatorList .addFirst (token );
53+ }
54+ else if (!stack .isEmpty () &&token .charAt (0 ) ==')' ) {
55+ // Add the operatorList to the result
56+ resultList .addAll (operatorList );
57+ operatorList .clear ();
58+ stack .pop ();
59+ }
60+ else if (token .charAt (0 ) =='+' ||token .charAt (0 ) =='-' )
61+ operatorList .addLast (token );// Add +, - to the end of list
62+ else if (token .charAt (0 ) =='*' ||token .charAt (0 ) =='/' )
63+ operatorList .addFirst (token );// Add +, - to the front of list
64+ else if (Character .isDigit (token .charAt (0 )))
65+ resultList .addLast (token );// Add digits to result list
66+ }
67+
68+ // Format the result string
69+ String result ="" ;
70+ resultList .addAll (operatorList );
71+ for (String e :resultList ) {
72+ result +=e +" " ;
73+ }
74+
75+ // return result
76+ return result ;
77+ }
78+
79+ /** Method Inserts blanks around (, ), +, -, /, and *. */
80+ public static String insertBlanks (String s ) {
81+ String result ="" ;
82+
83+ for (int i =0 ;i <s .length ();i ++) {
84+ if (s .charAt (i ) =='(' ||s .charAt (i ) ==')' ||
85+ s .charAt (i ) =='+' ||s .charAt (i ) =='-' ||
86+ s .charAt (i ) =='*' ||s .charAt (i ) =='/' )
87+ result +=" " +s .charAt (i ) +" " ;
88+ else
89+ result +=s .charAt (i );
90+ }
91+
92+ return result ;
93+ }
94+ }
