infixToPostfix/infixToPostfix.java at main · ajbot22/infixToPostfix · 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
119
120
121
122
123
124
125
126
127
128
129
//Done in collaboration between Aj Botticelli & Zach Brown
import java.util.*;
import javax.swing.JOptionPane;

public class infixToPostfix {
    public static void main(String[] args) {
        Stack<Character> operatorStack = new Stack<Character>();
        Stack<Double> valueStack = new Stack<Double>();
        String infix = JOptionPane.showInputDialog("Enter Infix: ");
        postfixEvaluator(infixConverter(infix,operatorStack),valueStack);
    }

    public static StringBuilder infixConverter(String infix, Stack<Character> operatorStack){
        StringBuilder postfixExpression = new StringBuilder();
        // could use a switch statement in a method, but this is much cleaner
        // set a precedence value to each operator
        HashMap<Character, Integer> precedenceHash = new HashMap<Character, Integer>() {
            {
                put('*', 2);
                put('/', 2);
                put('%', 2);
                put('+', 1);
                put('-', 1);
                put('(', 0);
                put(')', 0);
            }
        };
        for (int i = 0; i < infix.length(); i++) {
            char value = infix.charAt(i);
            switch (value) {
                case' ':
                    break;
                case '*':
                case '/':
                case '%':
                case '+':
                case '-':
                    // ----------------everything from here on out refers to an operator----------------
                    // if operator stack is empty push it
                    if (operatorStack.empty())
                        operatorStack.push(value);
                    else {

                    // if precedence of value is greater than the precedence of top of the operator stack, push it
                        if (precedenceHash.get(value) > precedenceHash.get(operatorStack.peek()))
                            operatorStack.push(value);
                        // if precedence of value is less than or equal to the precedence of top of operator stack,
                        // pop operators into operatorstack until precedence of top of operator stack is lower than the
                        // original value's precedent
                        else if (precedenceHash.get(value) <= precedenceHash.get(operatorStack.peek())) {
                            while (!operatorStack.empty()
                                    && precedenceHash.containsKey(operatorStack.peek())
                                    && precedenceHash.get(value) <= precedenceHash.get(operatorStack.peek()))
                            {
                                postfixExpression.append(operatorStack.pop()+" ");
                            }
                            operatorStack.push(value);
                        }
                    }
                    break;

                case ')':
                    // pop operators off the stack until you encounter an open parenthesis, and pop that out of the stack
                    while (!operatorStack.empty() && operatorStack.peek() != '(') postfixExpression.append(operatorStack.pop()+" ");
                    operatorStack.pop();
                    break;
                case '(':
                    // push no matter what
                    operatorStack.push(value);
                    break;
                default:
                    // operand
                    while (i < infix.length() && Character.isDigit(infix.charAt(i))) {
                        postfixExpression.append(infix.charAt(i));
                        i++;
                    }
                    postfixExpression.append(' ');
                    i--; // account for extra loop
                    break;
            }
        }
        //pop the rest of the stack to get rest of operators left in the stack
        while (!operatorStack.empty()) {
            postfixExpression.append(operatorStack.pop()+" ");
        }
        // print and return the postfix expression
        System.out.println("Infix Expression: "+infix);
        System.out.println("Postfix Expression: " + postfixExpression);
        return postfixExpression;
    }

    public static Double postfixEvaluator(StringBuilder postfix, Stack<Double> valueStack){
        Double postfixEval;
        String[] postfixArray = postfix.toString().split(" "); //seperate postfix expression

        for(int j=0;j<postfixArray.length;j++){
            // Manipulating data types to seperate operands and operators
            String operand = postfixArray[j];
            char operator = operand.charAt(0);
            // Push operands into the stack
            if(Character.isDigit(operator)){
                //System.out.println("operand: "+Double.parseDouble(operand));
                valueStack.push(Double.parseDouble(operand));
            }
            // Handle operators and arithmetic
            else{
                Double temp1 = valueStack.pop();
                Double temp2 = valueStack.pop();
                switch(operator){
                    case'*':valueStack.push(temp2*temp1);
                        break;
                    case'/':valueStack.push(temp2/temp1);
                        break;
                    case'%':valueStack.push(temp2%temp1);
                        break;
                    case'+':valueStack.push(temp2+temp1);
                        break;
                    case'-':valueStack.push(temp2-temp1);
                        break;
                }
            }
            //System.out.println("        Top of stack: "+valueStack.peek());
        }
        // pop, print, and return the postfix evaluation
        postfixEval=valueStack.pop();
        System.out.println("Evaluated postfix expression: "+ postfixEval);
        return postfixEval;
    }
}