USING “Data Abstraction and Problem Solving with Java”, 3nd Edition, Addison Wes
ID: 3662590 • Letter: U
Question
USING “Data Abstraction and Problem Solving with Java”, 3nd Edition, Addison Wesley, 2010 (paperback), ISBN-10: 0132122308 , ISBN-13: 9780132122306
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
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
} // end if
FIND A TERM
// the grammar specifies that an expression is either a
// a single term or a term followed by a * or a /,
// which then must be followed by a second factor
Find a factor
If (the next symbol is a * or a /) {
Find a factor
} // end if
Find A FACTOR
// the grammar specifies that an expression is either a
// 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
} // end if
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
Ans:
import java.io.*;
import java.io.IOException;
public class CheckLegal
{
private Stack s;
private String input;
public CheckLegal(String in)
{
input =in;
int stackSize= input.length();
s=new Stack(stackSize);
}
public void doCheck()
{
int j= s.head;
while(j==0)
{
char ch=input.charAt(j);
if(Character.isLetter(ch))
{
s.pop();
}
else
break;
}
while(j==0)
{
if(ch=='+' || ch =='-')
{
s.pop();
}
else
break;
while(j==0)
{
if(ch=='*' || ch== '/')
{
s.pop();
}
else break;
}
}
if(s.IsEmpty())
{
System.out.println("the entered expression is according to specified grammer and is legal");
}
}
public static void main(String [] args) throws IOException
{
Scanner s1= new Scanner(System.in);
String input= s1.nextLine();
CheckLegal c= new CheckLegal(input);
}
}
Note : the Stack class can be given as in general:
class Stack {
private int maxSize;
private char[] stackArray;
private int top;
public Stack(int max) {
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) {
stackArray[++top] = j;
}
public char pop() {
return stackArray[top--];
}
public char peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.