-
Notifications
You must be signed in to change notification settings - Fork 51
/
InfixToPostfix_UsingStack.java
119 lines (104 loc) · 3.07 KB
/
InfixToPostfix_UsingStack.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
/*
* Infix expression to Postfix expression using stack
* You can also display what is in stack at each step
* Author Krishna Pai
* Date 1-Oct-2021
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
class MyCharStack{
public char[] chStack = new char[30];
public int top=-1;
public int max=30;
public boolean isStackFull() {
return top > max - 1;
}
public boolean isStackEmpty() {
return top < 0;
}
public void push(char c) {
top++;
if (isStackFull()) {
top--;
System.out.println("***Stack is full***");
}
else {
chStack[top]= c;
}
}
public char pop() {
if (isStackEmpty()) {
System.out.println("Stack is empty");
return 0;
} else {
char topElement = chStack[top];
top--;
return topElement;
}
}
public char peek() {
return chStack[top];
}
public void display(){
System.out.print("Stack: ");
for (int i = 0; i<= top ; i++) {
System.out.print(chStack[i]+ " ");
}
System.out.println("\n-------------------------------");
}
}
public class InfixToPostfix_UsingStack {
static MyCharStack op = new MyCharStack();
public static void main(String[] args) throws Exception {
System.out.println("----Infix to Postfix Conversion----");
System.out.println("Enter prefix expression: ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String infix = br.readLine();
String temp = infix.replace(" ", "");
System.out.println("*******************************");
System.out.println("Postfix Expression: "+ Output(temp));
}
static int precedence(char z) {
if (z == '+' || z == '-') {
return 1;
}
if (z == '*' || z == '/' || z == '%') {
return 2;
}
if (z == '^' || z == '$') {
return 3;
}
return 0;
}
static String Output(String infix) {
StringBuilder postfix = new StringBuilder();
char c;
for (int i = 0; i < infix.length(); i++) {
c = infix.charAt(i);
if (Character.isLetter(c)) {
postfix.append(c);
//System.out.println("Output: " + postfix);
}
else if (c == '(') {
op.push(c);
//op.display();
}
else if (c == ')'){
while (op.peek() != '(') {
postfix.append(op.pop());
}
op.pop();
// op.display();
}
else {
while (!op.isStackEmpty() && !(op.peek() == '(') && precedence(c) <= precedence(op.peek()))
postfix.append(op.pop());
op.push(c);
//op.display();
}
}
while (!op.isStackEmpty())
postfix.append(op.pop());
return postfix.toString();
}
}