USING Data Abstraction and Problem Solving with C 5th Editio

USING “Data Abstraction and Problem Solving with C++”, 5th Edition, Addison Wesley, 2006 (paperback), ISBN 0321433327 , ISBN-13: 9780321433329

The following is a grammar that allows you to omit parentheses in infix algebraic expression when the precedence rule remove ambiguity for example, a + b*c means a+ (b*c). however, the grammar does not permit left-to- right association when several operators have the same precedence. For example, a/b*c is illegal. notice that definitions introduce factors and terms.

< expression > = <term> | <term> + <term> | <term> - <term>

<term> = <factor > | < factor > * < factor > | < factor > / < factor >

<factor > = <letter> | (<expression>)

<letter>= a | b | … | z

The recognition algorithm is based on recursive chain of subtasks: find an expression \ ightarrow find a term \ ightarrow find a factor. What makes this a recursive chain is that find as expression uses find a term, which in turn uses find a factor. Find a factor either detects a base case or use find an expression, thus forming the recursive chain.

FIND AN EXPRESSION

// the grammar specifies that an expression is either

// a single term or a term followed by a + or a -,

// which then must be followed by a second term

Find a term

If (the next symbol is a + or a - )

{ Find a term }

FIND A TERM

// the grammar specifies that an expression is either a

// a single term or a term followed by a * or a /,

// which must then be followed by a second factor

Find a factor

If (the next symbol is a * or a /)

{ Find a factor }

Find A FACTOR

// the grammar specifies that an expression is either

// a single letter (the base case) or an

// expression enclosed in parentheses

If (the first symbol is a letter)

{ Done }

else if (the first symbol is a ‘(‘)

{ Find an expression starting at character after ‘(‘ Check for ‘)’ }

else

{ no factor exists }

Design and implement a class of infix expressions, as described by the given grammar. Include a method to recognize a legal infix expression.

Solution

Hope this will help-

import java.util.Stack;

public class EvaluateString
{
    public static int evaluate(String expression)
    {
        char[] tokens = expression.toCharArray();
        Stack<Integer> values = new Stack<Integer>();
        Stack<Character> ops = new Stack<Character>();
        for (int i = 0; i < tokens.length; i++)
        {
            if (tokens[i] == \' \')
                continue;

            if (tokens[i] >= \'0\' && tokens[i] <= \'9\')
            {
                StringBuffer sbuf = new StringBuffer();
                while (i < tokens.length && tokens[i] >= \'0\' && tokens[i] <= \'9\')
                    sbuf.append(tokens[i++]);
                values.push(Integer.parseInt(sbuf.toString()));
            }
            else if (tokens[i] == \'(\')
                ops.push(tokens[i]);
            else if (tokens[i] == \')\')
            {
                while (ops.peek() != \'(\')
                  values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                ops.pop();
            }
            else if (tokens[i] == \'+\' || tokens[i] == \'-\' ||
                     tokens[i] == \'*\' || tokens[i] == \'/\')
            {
                while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
                  values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                ops.push(tokens[i]);
            }
        }
        while (!ops.empty())
            values.push(applyOp(ops.pop(), values.pop(), values.pop()));
        return values.pop();
    }
    public static boolean hasPrecedence(char op1, char op2)
    {
        if (op2 == \'(\' || op2 == \')\')
            return false;
        if ((op1 == \'*\' || op1 == \'/\') && (op2 == \'+\' || op2 == \'-\'))
            return false;
        else
            return true;
    }
    public static int applyOp(char op, int b, int a)
    {
        switch (op)
        {
        case \'+\':
            return a + b;
        case \'-\':
            return a - b;
        case \'*\':
            return a * b;
        case \'/\':
            if (b == 0)
                throw new UnsupportedOperationException(\"Cannot divide by zero\");
            return a / b;
        }
        return 0;
    }

    public static void main(String[] args)
    {
        System.out.println(EvaluateString.evaluate(\"10 + 2 * 6\"));//a+b*C expression
    }
}