Data Structures using java Chapter 7 Q 6. consider simpls infix expression that
ID: 3764927 • Letter: D
Question
Data Structures using java
Chapter 7 Q 6.
consider simpls infix expression that consist of single-digit operands; the operators +, -, *, %,/; and parentheses. assume that unary operators are illegal and that the expression contains no embedded spaces.
Desing and implement a class for an infix calculators. use the algorithm given in this chapter to convert the infix expressions to postfix form and to evaluate the resulting postfix expressions, Note that if the methods eveluate and get Postfix are called befoer the convert postfix method, then the excption illegalStateExcption should be thrown by these methods.
class Calculator {
public Calculator(String exp)
public string toString()
private boolean convertPostfix()
public String getpostfic() throws illegalStateExceptin
public int evaluate () throws illegalStateExceptin
}
You can use the PostfixCalculator class designed for Problem 4 to implement the evaluate() method of this question.
Explanation / Answer
/**
* @author Srinivas
*
*/
public class Calculator {
String exp, postFix;
int value;
public Calculator(String exp) {
this.exp = exp;
postFix = "";
}
@Override
public String toString() {
return exp;
}
private boolean convertPostfix() {
// Use StringBuilder to append string is faster than
// String concatenation
StringBuilder sb = new StringBuilder();
// Use a stack to track operations
Stack<Character> op = new Stack<Character>();
// Convert expression string to char array
char[] chars = exp.toCharArray();
// The length of expression character
int N = chars.length;
for (int i = 0; i < N; i++) {
char ch = chars[i];
if (Character.isDigit(ch)) {
// Number, simply append to the result
while (Character.isDigit(chars[i])) {
sb.append(chars[i++]);
}
// Use space as delimiter
sb.append(' ');
} else if (ch == '(') {
// Left parenthesis, push to the stack
op.push(ch);
} else if (ch == ')') {
// Right parenthesis, pop and append to the result until meet
// the left parenthesis
while (op.peek() != '(') {
sb.append(op.pop()).append(' ');
}
// Don't forget to pop the left parenthesis out
op.pop();
} else if (isOperator(ch)) {
// Operator, pop out all higher priority operators first and
// then push it to the stack
while (!op.isEmpty() && priority(op.peek()) >= priority(ch)) {
sb.append(op.pop()).append(' ');
}
op.push(ch);
}
}
// Finally pop out whatever left in the stack and append to the result
while (!op.isEmpty()) {
sb.append(op.pop()).append(' ');
}
System.out.println("sb==" + sb);
postFix = sb.toString();
return true;
}
private static int priority(char operator) {
switch (operator) {
case '^':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
}
return 0;
}
public String getpostfic() throws IllegalStateException {
if (postFix.equals("")) {
throw new IllegalStateException();
}
return postFix;
}
public int evaluate() throws IllegalStateException {
if (postFix.equals("")) {
throw new IllegalStateException();
}
Stack<Integer> nums = new Stack<Integer>();
String expr[] = postFix.split(" ");
for (int i = 0; i < expr.length; i++) {
String elt = expr[i];
if (elt.equals("+")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a + b));
} else if (elt.equals("-")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a - b));
} else if (elt.equals("*")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a * b));
} else if (elt.equals("/")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a / b));
} else if (elt.equals("^")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a ^ b));
} else { // it must be a number
int x = Integer.parseInt(elt);
nums.push(new Integer(x));
}
}
return nums.pop().intValue();
}
private static boolean isOperator(char ch) {
return ch == '^' || ch == '*' || ch == '/' || ch == '+' || ch == '-';
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.