Write a program that asks the user for an infix expression, evaluates it, and ou

Question

Write a program that asks the user for an infix expression, evaluates it, and outputs the result.

Assume the operands are doubles and the operators are of four types: +, -, *, and /. You may use Java's Stack class.

The problem can be solved using two stacks, named operandStack and operatorStack, for storing operands and operators, respectively. Operands and operators are pushed into the stacks before they are processed. When an operator is processed, it is popped from operatorStack and applied to the first two operands from operandStack (the two operands are popped from operandStack). The re- sultant value is pushed back to operandStack.

The algorithm proceeds in two phases:

Phase 1: Scanning expression.

The program scans the expression from left to right to extract operands, operators, and the parentheses.

(a) If the extracted item is an operand, push it into operandStack.

(b) If the extracted item is a + or - operator, process all the operators at the

top of operatorStack, push the extracted operator to operatorStack.

(c) If the extracted item is a * or / operator, process all the operators * and / at the top of operatorStack, push the extracted operator to operatorStack.

(d) If the extracted item is a ( symbol, push it to operatorStack.

(e) If the extracted item is a ) symbol, repeatedly process the operators from

the top of operatorStack until seeing the ( symbol on the stack.

Phase 2: Clearing stack.

Repeatedly process the operators from the top of operatorStack until operatorStack is empty.

Explanation / Answer

import java.util.Stack; import java.util.StringTokenizer; import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; public class Evaluator { private static final int EOL = 0; private static final int VALUE = 1; private static final int OPAREN = 2; private static final int CPAREN = 3; private static final int EXP = 4; private static final int MULT = 5; private static final int DIV = 6; private static final int PLUS = 7; private static final int MINUS = 8; private static class Precedence { public int inputSymbol; public int topOfStack; public Precedence( int inSymbol, int topSymbol ) { inputSymbol = inSymbol; topOfStack = topSymbol; } } // PrecTable matches order of Token enumeration private static Precedence [ ] precTable = new Precedence[ ] { new Precedence( 0, -1 ), // EOL new Precedence( 0, 0 ), // VALUE new Precedence( 100, 0 ), // OPAREN new Precedence( 0, 99 ), // CPAREN new Precedence( 6, 5 ), // EXP new Precedence( 3, 4 ), // MULT new Precedence( 3, 4 ), // DIV new Precedence( 1, 2 ), // PLUS new Precedence( 1, 2 ) // MINUS }; private static class Token { public Token( ) { this( EOL ); } public Token( int t ) { this( t, 0 ); } public Token( int t, long v ) { type = t; value = v; } public int getType( ) { return type; } public long getValue( ) { return value; } private int type = EOL; private long value = 0; } private static class EvalTokenizer { public EvalTokenizer( StringTokenizer is ) { str = is; } /** * Find the next token, skipping blanks, and return it. * For VALUE token, place the processed value in currentValue. * Print error message if input is unrecognized. */ public Token getToken( ) { long theValue; if( !str.hasMoreTokens( ) ) return new Token( ); String s = str.nextToken( ); if( s.equals( " " ) ) return getToken( ); if( s.equals( "^" ) ) return new Token( EXP ); if( s.equals( "/" ) ) return new Token( DIV ); if( s.equals( "*" ) ) return new Token( MULT ); if( s.equals( "(" ) ) return new Token( OPAREN ); if( s.equals( ")" ) ) return new Token( CPAREN ); if( s.equals( "+" ) ) return new Token( PLUS ); if( s.equals( "-" ) ) return new Token( MINUS ); try { theValue = Long.parseLong( s ); } catch( NumberFormatException e ) { System.err.println( "Parse error" ); return new Token( ); } return new Token( VALUE, theValue ); } private StringTokenizer str; } /** * Construct an evaluator object. * @param s the string containing the expression. */ public Evaluator( String s ) { opStack = new Stack( ); postfixStack = new Stack( ); str = new StringTokenizer( s, "+*-/^() ", true ); opStack.push( new Integer( EOL ) ); } // The only publicly visible routine /** * Public routine that performs the evaluation. * Examine the postfix machine to see if a single result is * left and if so, return it; otherwise print error. * @return the result. */ public long getValue( ) { EvalTokenizer tok = new EvalTokenizer( str ); Token lastToken; do { lastToken = tok.getToken( ); processToken( lastToken ); } while( lastToken.getType( ) != EOL ); if( postfixStack.isEmpty( ) ) { System.err.println( "Missing operand!" ); return 0; } long theResult = postFixTopAndPop( ); if( !postfixStack.isEmpty( ) ) System.err.println( "Warning: missing operators!" ); return theResult; } private Stack opStack; // Operator stack for conversion private Stack postfixStack; // Stack for postfix machine private StringTokenizer str; // StringTokenizer stream /** * Internal method that hides type-casting. */ private long postFixTopAndPop( ) { return ( (Long) ( postfixStack.pop( ) ) ).longValue( ); } /** * Another internal method that hides type-casting. */ private int opStackTop( ) { return ( (Integer) ( opStack.peek( ) ) ).intValue( ); } /** * After a token is read, use operator precedence parsing * algorithm to process it; missing opening parentheses * are detected here. */ private void processToken( Token lastToken ) { int topOp; int lastType = lastToken.getType( ); switch( lastType ) { case VALUE: postfixStack.push( new Long( lastToken.getValue( ) ) ); return; case CPAREN: while( ( topOp = opStackTop( ) ) != OPAREN && topOp != EOL ) binaryOp( topOp ); if( topOp == OPAREN ) opStack.pop( ); // Get rid of opening parentheseis else System.err.println( "Missing open parenthesis" ); break; default: // General operator case while( precTable[ lastType ].inputSymbol

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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