Untitled

 avatar
unknown
plain_text
2 years ago
4.2 kB
5
Indexable
import java.util.*;

public class InfixToPostfix {
    // A utility function to return precedence of a given operator
    // Higher returned value means higher precedence
    static int precedence(char ch) {
        switch (ch) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
        }
        return -1;
    }
    
    // The main function to convert infix expression to postfix expression
    static String infixToPostfix(String expression) {
        // Initialize a new empty stack
        Stack<Character> stack = new Stack<>();
        String result = "";
        
        // Loop through each character in the expression
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            
            // If the current character is an operand, add it to the result
            if (Character.isLetterOrDigit(c))
                result += c;
            
            // If the current character is a left parenthesis, push it onto the stack
            else if (c == '(')
                stack.push(c);
            
            // If the current character is a right parenthesis, pop elements from the stack
            // and add them to the result until a matching left parenthesis is found
            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(')
                    result += stack.pop();
                
                if (!stack.isEmpty() && stack.peek() != '(')
                    return "Invalid Expression";
                else
                    stack.pop();
            }
            
            // If the current character is an operator, pop operators from the stack
            // and add them to the result if their precedence is greater than or equal to
            // the precedence of the current operator, then push the current operator onto the stack
            else {
                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek()))
                    result += stack.pop();
                
                stack.push(c);
            }
        }
        
        // Pop any remaining operators from the stack and add them to the result
        while (!stack.isEmpty())
            result += stack.pop();
        
        return result;
    }
    
    // A utility function to evaluate a postfix expression
    static int evaluatePostfix(String expression) {
        // Initialize a new empty stack
        Stack<Integer> stack = new Stack<>();
        
        // Loop through each character in the expression
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            
            // If the current character is an operand, push it onto the stack
            if (Character.isDigit(c)) {
                int num = 0;
                while (Character.isDigit(c)) {
                    num = num * 10 + (int) (c - '0');
                    i++;
                    if (i < expression.length())
                        c = expression.charAt(i);
                    else
                        break;
                }
                i--;
                stack.push(num);
            }
            
            // If the current character is an operator, pop two operands from the stack
            // and apply the operator to them, then push the result back onto the stack
            else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                
                switch (c) {
                    case '+':
                        stack.push(operand1 + operand2);
                        break;
                    case '-':
                        stack.push(operand1 - operand2);
                        break;
                    case '*':
                        stack.push(operand1 * operand2);
                        break;
                    case '/':
                        stack
Editor is loading...