8000 Merge pull request #1964 from TheAlgorithms/infix2posfix · JavaInCloud/Java@25b3ff4 · GitHub
[go: up one dir, main page]
Skip to content

Commit 25b3ff4

Browse files
realDuYuanChaorealDuYuanChao
authored
Merge pull request TheAlgorithms#1964 from TheAlgorithms/infix2posfix
Infix2posfix
2 parents 2e6c7b4 + 6015137 commit 25b3ff4

File tree

3 files changed

+57
-0
lines changed

3 files changed

+57
-0
lines changed

‎.github/workflows/checkstyle.yml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ jobs:
2020
- name: Commit Format changes
2121
if: failure()
2222
run: |
23+
git diff
2324
git config --global user.name github-actions
2425
git config --global user.email '${GITHUB_ACTOR}@users.noreply.github.com'
2526
git remote set-url origin https://x-access-token:${{ secrets.GITHUB_TOKEN }}@github.com/$GITHUB_REPOSITORY

‎DIRECTORY.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -75,6 +75,7 @@
7575
* Stacks
7676
* [BalancedBrackets](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Stacks/BalancedBrackets.java)
7777
* [DecimalToAnyUsingStack](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Stacks/DecimalToAnyUsingStack.java)
78+
* [InfixToPostfix](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Stacks/InfixToPostfix.java)
7879
* [NodeStack](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Stacks/NodeStack.java)
7980
* [StackArray](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Stacks/StackArray.java)
8081
* [StackArrayList](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Stacks/StackArrayList.java)

‎DataStructures/Stacks/InfixToPostfix.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package DataStructures.Stacks;
2+
3+
import java.util.Stack;
4+
5+
public class InfixToPostfix {
6+
public static void main(String[] args) throws Exception {
7+
assert "32+".equals(infix2PostFix("3+2"));
8+
assert "123++".equals(infix2PostFix("1+(2+3)"));
9+
assert "34+5*6-".equals(infix2PostFix("(3+4)*5-6"));
10+
}
11+
12+
public static String infix2PostFix(String infixExpression) throws Exception {
13+
if (!BalancedBrackets.isBalanced(infixExpression)) {
14+
throw new Exception("invalid expression");
15+
}
16+
StringBuilder output = new StringBuilder();
17+
Stack<Character> stack = new Stack<>();
18+
for (char element : infixExpression.toCharArray()) {
19+
if (Character.isLetterOrDigit(element)) {
20+
output.append(element);
21+
} else if (element == '(') {
22+
stack.push(element);
23+
} else if (element == ')') {
24+
while (!stack.isEmpty() && stack.peek() != '(') {
25+
output.append(stack.pop());
26+
}
27+
stack.pop();
28+
} else {
29+
while (!stack.isEmpty() && precedence(element) <= precedence(stack.peek())) {
30+
output.append(stack.pop());
31+
}
32+
stack.push(element);
33+
}
34+
}
35+
while (!stack.isEmpty()) {
36+
output.append(stack.pop());
37+
}
38+
return output.toString();
39+
}
40+
41+
private static int precedence(char operator) {
42+
switch (operator) {
43+
case '+':
44+
case '-':
45+
return 0;
46+
case '*':
47+
case '/':
48+
return 1;
49+
case '^':
50+
return 2;
51+
default:
52+
return -1;
53+
}
54+
}
55+
}

0 commit comments

Comments
 (0)
0