Java Coding:

Write a program that uses the combined algorithm below to evaluate infix expressions entered by the user. The program should support infix expressions involving any double values (positive, negative, or zero) and any combination of opening/closing parentheses () and these operators: + addition - subtraction * multiplication / division ^ exponentiation (e.g., 7^2 = 49) keep in mind this ones precedence is higher than * or / You can use the built-in java.util.Stack class to keep track of your operands and operators. A few assumptions you can make to simplify things a bit: All tokens in the infix expression are separated by spaces. The infix expression is well balanced with respect to parentheses, and properly formatted. Regular parentheses are used for all levels of nesting (no curly braces or square brackets, ever). The unary minus (to represent negative values) appears only in front of numbers, never in front of parentheses. There is no space between a unary minus and its associated number.

You can evaluate an infix expression by using two separate algorithms: one to convert the infix expression into postfix, and one to evaluate the postfix expression. This requires two passes in all. Its possible to execute both algorithms at the same time, allowing you to evaluate an infix expression in a single pass. Heres how the combined algorithm works: a. Maintain two stacks: one for operands and one for operators/parentheses. b. Scan the infix expression one token at a time, from left to right. Here a token is defined as an operand, operator, or parentheses symbol. i. If the token is an operand, push it onto the operand stack. ii. If the token is an operator or a parentheses symbol, handle it as described in the infix to postfix conversion algorithm. Every time you pop a non-parentheses operator off the operator stack, also pop the top two elements off the operand stack, perform the indicated operation, and push the result back onto the operand stack. c. Once all tokens in the infix expression have been scanned, pop the remaining operators off the operator stack while also modifying the operand stack as described in step b(ii). d. The final result will be the top (and only) element left on the operand stack at the end.

Heres an example of a running program; the underlined portions indicate user input.

Enter an infix expression with spaces between all tokens, X to exit:

1 + 2 Result: 3.0 Enter an infix expression with spaces between all tokens, X to exit: 1 + 2 * ( 10 - 4 ) Result: 13.0 Enter an infix expression with spaces between all tokens, X to exit: ( 1 + 2 ) * ( 10 - 4 ) Result: 18.0 Enter an infix expression with spaces between all tokens, X to exit: ( 1 + 2 ) * ( -4 + 10 ) ^ 2 Result: 108.0 Enter an infix expression with spaces between all tokens, X to exit: 2 * ( 1 - ( 4 + 3 ) ) Result: -12.0