Arithmetic Expression Evaluation

Evaluating stendard infix expressions can be complex due to operator precedence and parentheses handling. While rceursive approaches or stacks can manage these complexities, there's a more elegant solution: Reverse Polish Notation (RPN).

public int evaluateExpression(String expression) {
    expression = expression.trim();
    Deque<Integer> values = new ArrayDeque<>();
    
    int currentNumber = 0;
    char operation = '+';
    char[] chars = expression.toCharArray();
    
    for (int index = 0; index < chars.length; index++) {
        char ch = expression.charAt(index);
        
        if (ch == ' ') continue;
        
        if (Character.isDigit(ch)) {
            currentNumber = currentNumber * 10 + (ch - '0');
        }
        
        if (ch == '(') {
            int endIndex = findMatchingParenthesis(chars, index);
            currentNumber = evaluateExpression(expression.substring(index + 1, endIndex));
            index = endIndex;
        }
        
        if (!Character.isDigit(ch) || index == chars.length - 1) {
            processOperation(values, currentNumber, operation);
            currentNumber = 0;
            operation = ch;
        }
    }
    
    return calculateFinalResult(values);
}

private int findMatchingParenthesis(char[] chars, int startIndex) {
    int count = 1;
    int position = startIndex + 1;
    
    while (count > 0) {
        if (chars[position] == '(') count++;
        if (chars[position] == ')') count--;
        position++;
    }
    
    return position - 1;
}

private void processOperation(Deque<Integer> stack, int number, char op) {
    switch (op) {
        case '+': stack.push(number); break;
        case '-': stack.push(-number); break;
        case '*': stack.push(stack.pop() * number); break;
        case '/': stack.push(stack.pop() / number); break;
    }
}

private int calculateFinalResult(Deque<Integer> stack) {
    int result = 0;
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

Converting Infix to RPN

RPN eliminates the need for parentheses by placing operators after their operands. For example, the infix expression "9+(3-1)*3+10/2" becomes "9 3 1- 3*+ 10 2 /+" in RPN form.

private static final Map<Character, Integer> priority = new HashMap<>();
static {
    priority.put('+', 1);
    priority.put('-', 1);
    priority.put('*', 2);
    priority.put('/', 2);
    priority.put('^', 3);
}

public String convertToRPN(String infix) {
    StringBuilder result = new StringBuilder();
    Stack<Character> operators = new Stack<>();
    
    for (char token : infix.toCharArray()) {
        if (Character.isDigit(token)) {
            result.append(token);
        } else if (token == '(') {
            operators.push(token);
        } else if (token == ')') {
            while (!operators.isEmpty() && operators.peek() != '(') {
                result.append(operators.pop());
            }
            if (!operators.isEmpty()) operators.pop();
        } else {
            while (!operators.isEmpty() && 
                   operators.peek() != '(' && 
                   priority.get(token) <= priority.get(operators.peek())) {
                result.append(operators.pop());
            }
            operators.push(token);
        }
    }
    
    while (!operators.isEmpty()) {
        result.append(operators.pop());
    }
    
    return result.toString();
}

RPN Expression Evaluation

To evaluate an RPN expression, traverse from left to right. Push numbers onto a stack, and when encountering operators, pop two operands, perform the operation, and push the result back.

public int computeRPN(String[] rpnTokens) {
    Stack<Integer> computationStack = new Stack<>();
    
    for (String element : rpnTokens) {
        if (isOperator(element)) {
            int operand1 = computationStack.pop();
            int operand2 = computationStack.pop();
            
            int result = performCalculation(operand2, operand1, element);
            computationStack.push(result);
        } else {
            computationStack.push(Integer.parseInt(element));
        }
    }
    
    return computationStack.pop();
}

private boolean isOperator(String token) {
    return "+".equals(token) || "-".equals(token) || 
           "*".equals(token) || "/".equals(token);
}

private int performCalculation(int left, int right, String operator) {
    switch (operator) {
        case "+": return left + right;
        case "-": return left - right;
        case "*": return left * right;
        case "/": return left / right;
        default: throw new IllegalArgumentException("Invalid operator");
    }
}

Additional Considerations

Prefix notation (Polish Notation) also exists, where operators precede operands. Unlike RPN which processes left-to-right, prefix evaluation requires right-to-left traversal with similar operational principles.