Java Coding: Write a program that uses the combined algorithm below to evaluate

Question

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 one’s precedence is higher than * or / You can use the built-in java.util.Stack<E> 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. It’s possible to execute both algorithms at the same time, allowing you to evaluate an infix expression in a single pass. Here’s 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.

Here’s 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

Explanation / Answer

Hi Dear,

Please find my implementation:

Output:

Enter an infix expression with spaces between all tokens, X to exit: 2 * ( 1 - ( 4 + 3 ) )
Result: -12.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: ( 1 + 2 ) * ( 10 - 4 )
Result: 18.0

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

Process finished with exit code 0

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.