USING “Data Abstraction and Problem Solving with C++”, 5th Edition, Addison Wesl
ID: 3929952 • Letter: U
Question
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.
Explanation / Answer
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
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.