/
PostfixToInfix.java
131 lines (103 loc) · 3.8 KB
/
PostfixToInfix.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package com.thealgorithms.stacks;
import java.util.Stack;
/**
* Postfix to Infix implementation via Stack
*
* Function: String getPostfixToInfix(String postfix)
* Returns the Infix Expression for the given postfix parameter.
*
* Avoid using parentheses/brackets/braces for the postfix string.
* Postfix Expressions don't require these.
*
*
* @author nikslyon19 (Nikhil Bisht)
*
*/
public final class PostfixToInfix {
private PostfixToInfix() {
}
public static boolean isOperator(char token) {
switch (token) {
case '+':
case '-':
case '/':
case '*':
case '^':
return true;
}
return false;
}
public static boolean isValidPostfixExpression(String postfix) {
/* Postfix expression length should NOT be less than 3 */
if (postfix.length() < 3) return false;
/* First two characters should NOT be operators */
if (isOperator(postfix.charAt(0))) return false;
if (isOperator(postfix.charAt(1))) return false;
int operandCount = 0;
int operatorCount = 0;
/* Traverse the postfix string to check if --> Number of operands = Number of operators + 1
*/
for (int i = 0; i < postfix.length(); i++) {
char token = postfix.charAt(i);
if (isOperator(token)) {
operatorCount++;
if (operatorCount >= operandCount) return false;
} else {
if (operatorCount == 0) {
operandCount++;
continue;
}
if (operandCount != operatorCount + 1) return false;
/* Operand count is set to 2 because:-
*
* 1) the previous set of operands & operators combined have become a single valid
* expression, which could be considered/assigned as a single operand.
*
* 2) the operand in the current iteration.
*/
operandCount = 2;
/* Reset operator count */
operatorCount = 0;
}
}
return (operandCount == operatorCount + 1);
}
public static String getPostfixToInfix(String postfix) {
String infix = "";
if (postfix.isEmpty()) return infix;
/* Validate Postfix expression before proceeding with the Infix conversion */
if (!isValidPostfixExpression(postfix)) {
throw new IllegalArgumentException("Invalid Postfix Expression");
}
Stack<String> stack = new Stack<>();
StringBuilder valueString = new StringBuilder();
String operandA, operandB;
char operator;
for (int index = 0; index < postfix.length(); index++) {
char token = postfix.charAt(index);
if (!isOperator(token)) {
stack.push(Character.toString(token));
continue;
}
operator = token;
operandB = stack.pop();
operandA = stack.pop();
valueString.append('(');
valueString.append(operandA);
valueString.append(operator);
valueString.append(operandB);
valueString.append(')');
stack.push(valueString.toString());
valueString.setLength(0);
}
infix = stack.pop();
return infix;
}
public static void main(String[] args) {
assert getPostfixToInfix("ABC+/").equals("(A/(B+C))");
assert getPostfixToInfix("AB+CD+*").equals("((A+B)*(C+D))");
assert getPostfixToInfix("AB+C+D+").equals("(((A+B)+C)+D)");
assert getPostfixToInfix("ABCDE^*/-").equals("(A-(B/(C*(D^E))))");
assert getPostfixToInfix("AB+CD^/E*FGH+-^").equals("((((A+B)/(C^D))*E)^(F-(G+H)))");
}
}