Convert an infix expression to postfix problem

Input: "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
Output: "3 4 2 * 1 5 - 2 3 ^ ^ / +"
Explanation: The infix expression "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" is converted to the postfix expression "3 4 2 * 1 5 - 2 3 ^ ^ / +".

Input: "a + b * c"
Output: "a b c * +"
Explanation: The infix expression "a + b * c" is converted to the postfix expression "a b c * +".

public class Solution {
    public String toPostfix(String infix) {
        StringBuilder output = new StringBuilder();
        Stack<Character> operators = new Stack<>();

        Map<Character, Integer> precedence = new HashMap<>();
        precedence.put('^', 4);
        precedence.put('*', 3);
        precedence.put('/', 3);
        precedence.put('+', 2);
        precedence.put('-', 2);

        Map<Character, Boolean> rightAssociative = new HashMap<>();
        rightAssociative.put('^', true); // '^' is right associative

        for (int i = 0; i < infix.length(); i++) {
            char token = infix.charAt(i);

            if (Character.isWhitespace(token)) {
                continue;
            } else if (Character.isLetterOrDigit(token)) {
                output.append(token).append(' ');
            } else if (token == '(') {
                operators.push(token);
            } else if (token == ')') {
                while (!operators.isEmpty() && operators.peek() != '(') {
                    output.append(operators.pop()).append(' ');
                }
                operators.pop(); // Remove the '('
            } else if (precedence.containsKey(token)) {
                while (!operators.isEmpty() && precedence.containsKey(operators.peek()) &&
                        ((rightAssociative.getOrDefault(token, false) && precedence.get(token) < precedence.get(operators.peek())) ||
                        (!rightAssociative.getOrDefault(token, false) && precedence.get(token) <= precedence.get(operators.peek())))) {
                    output.append(operators.pop()).append(' ');
                }
                operators.push(token);
            }
        }

        while (!operators.isEmpty()) {
            output.append(operators.pop()).append(' ');
        }

        return output.toString().trim();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.toPostfix("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")); // Output: 3 4 2 * 1 5 - 2 3 ^ ^ / +
        System.out.println(solution.toPostfix("a + b * c")); // Output: a b c * +
    }
}

class Solution:
    def toPostfix(self, infix: str) -> str:
        output: List[str] = []
        operators: List[str] = []

        precedence = {'^': 4, '*': 3, '/': 3, '+': 2, '-': 2}
        right_associative = {'^': True}  # '^' is right associative

        i = 0
        while i < len(infix):
            token = infix[i]

            if token.isspace():
                i += 1
                continue
            elif token.isalnum():  # token is an operand
                output.append(token)
            elif token == '(':
                operators.append(token)
            elif token == ')':
                while operators and operators[-1] != '(':
                    output.append(operators.pop())
                operators.pop()  # Remove the '('
            elif token in precedence:
                while (operators and operators[-1] in precedence and
                    ((token in right_associative and precedence[token] < precedence[operators[-1]]) or
                        (token not in right_associative and precedence[token] <= precedence[operators[-1]]))):
                    output.append(operators.pop())
                operators.append(token)
            i += 1

        while operators:
            output.append(operators.pop())

        return ' '.join(output)

# Test the implementation
sol = Solution()
print(sol.toPostfix("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"))  # Output: 3 4 2 * 1 5 - 2 3 ^ ^ / +
print(sol.toPostfix("a + b * c"))  # Output: a b c * +