100-Days-of-Java-Coding/Day 72 at main · Shailesh161/100-Days-of-Java-Coding · GitHub

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

import java.util.*;
class GFG
{

static boolean isOperator(char c)
{
	return (!(c >= 'a' && c <= 'z') &&
			!(c >= '0' && c <= '9') &&
			!(c >= 'A' && c <= 'Z'));
}


static int getPriority(char C)
{
	if (C == '-' || C == '+')
		return 1;
	else if (C == '*' || C == '/')
		return 2;
	else if (C == '^')
		return 3;
	return 0;
}

static String infixToPrefix(String infix)
{

	Stack<Character> operators = new Stack<Character>();
	Stack<String> operands = new Stack<String>();

	for (int i = 0; i < infix.length(); i++)
	{
		if (infix.charAt(i) == '(')
		{
			operators.push(infix.charAt(i));
		}

		else if (infix.charAt(i) == ')')
		{
			while (!operators.empty() &&
				operators.peek() != '(')
				{

				// operand 1
				String op1 = operands.peek();
				operands.pop();

				// operand 2
				String op2 = operands.peek();
				operands.pop();

				// operator
				char op = operators.peek();
				operators.pop();

				String tmp = op + op2 + op1;
				operands.push(tmp);
			}

			operators.pop();
		}


		else if (!isOperator(infix.charAt(i)))
		{
			operands.push(infix.charAt(i) + "");
		}

		else
		{
			while (!operators.empty() &&
				getPriority(infix.charAt(i)) <=
					getPriority(operators.peek()))
				{

				String op1 = operands.peek();
				operands.pop();

				String op2 = operands.peek();
				operands.pop();

				char op = operators.peek();
				operators.pop();

				String tmp = op + op2 + op1;
				operands.push(tmp);
			}

			operators.push(infix.charAt(i));
		}
	}


	while (!operators.empty())
	{
		String op1 = operands.peek();
		operands.pop();

		String op2 = operands.peek();
		operands.pop();

		char op = operators.peek();
		operators.pop();

		String tmp = op + op2 + op1;
		operands.push(tmp);
	}

	return operands.peek();
}

// Driver code
public static void main(String args[])
{
	String s = "(A-B/C)*(A/K-L)";
	System.out.println( infixToPrefix(s));
}
}