You are to write a program name calc.java that evaluates an infix expression ent
ID: 3681665 • Letter: Y
Question
You are to write a program name calc.java that evaluates an infix expression entered by the user. The expression may contain the following tokens:
(1) Integer constants (a series of decimal digits).
(2) x (representing a value to be supplied later).
(3) Binary operators (+, -, *, / and %).
(4) Parentheses
Spaces between tokens are allowed but not required. The program will convert the expression to postfix (RPN) form and display the converted expression. The program will repeatedly prompt the user for the value of x, displaying the value of the expression each time. When the user enters the letter q instead of a number, the program terminates.
The following example illustrates the behavior of the program (user input is in bold):
Porgram output is in italicized
Enter infix expression: (x + 1) * (x – 2) / 4
Converted expression: x 1 + x 2 - * 4 /
Enter value of x: 5
Answer to expression: 4
Enter value of x: 7
Answer to expression: 10
Enter value of x: q
If the infix expression contains an error of any kind, the program must display the message Error in expression (with an optional explanation) and then terminate. The following examples illustrate various types of errors:
Enter infix expression: 1 2 +
Error in expression!! No operator between operands. Also last token must be an operand.
Enter infix expression: 10.4
Error in expression!! Cannot accept floating point numbers.
Enter infix expression: 1 ( + 2)
Error in expression!! No operator between operand and left parentheses.
Enter infix expression: 5 – (x – 2))
Error in expression!! No matching left parentheses for a right parentheses.
Enter infix expression: 1 ** 2
Error in expression!! The * operator cannot be preceded by a * operator.
The output of your program must match the format illustrated in this example.
Here are some other additional requirements for this program:
(1) You must use stack objects during the translation from infix to postfix and during the evaluation of the postfix expression.
(2) Operators must have the correct precedence and associativity.
Explanation / Answer
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
class Stack {
char a[] = new char[100];
int top = -1;
void push(char c) {
try {
a[++top] = c;
} catch (StringIndexOutOfBoundsException e) {
System.out.println("Stack full , no room to push , size=100");
System.exit(0);
}
}
char pop() {
return a[top--];
}
boolean isEmpty() {
return (top == -1) ? true : false;
}
char peek() {
return a[top];
}
}
public class InfxToPostfx {
static Stack operators = new Stack();
public static void main(String argv[]) throws IOException {
String infix;
// create an input stream object
BufferedReader keyboard = new BufferedReader(new InputStreamReader(
System.in));
// get input from user
System.out.print(" Enter the algebraic expression in infix: ");
infix = keyboard.readLine();
String postFx = toPostfix(infix);
// output as postfix
System.out.println("The expression in postfix is:" + postFx);
if (postFx.contains("x")) {
String line = "";
do {
System.out.println("Enter value of X : ");
line = keyboard.readLine();
if (!"q".equalsIgnoreCase(line)) {
postFx = postFx.replaceAll("x", line);
System.out.println("Answer to expression : "
+ EvaluateString.evaluate(postFx));
}
} while (!line.equals("q"));
} else {
System.out.println("Answer to expression : "
+ EvaluateString.evaluate(postFx));
}
}
private static String toPostfix(String infix)
// converts an infix expression to postfix
{
char symbol;
String postfix = "";
for (int i = 0; i < infix.length(); ++i)
// while there is input to be read
{
symbol = infix.charAt(i);
// if it's an operand, add it to the string
if (symbol != ' ') {
if (Character.isLetter(symbol) || Character.isDigit(symbol))
postfix = postfix + " " + symbol;
else if (symbol == '(')
// push (
{
operators.push(symbol);
} else if (symbol == ')')
// push everything back to (
{
while (operators.peek() != '(') {
postfix = postfix + " " + operators.pop();
}
operators.pop(); // remove '('
} else
// print operators occurring before it that have greater
// precedence
{
while (!operators.isEmpty() && !(operators.peek() == '(')
&& prec(symbol) <= prec(operators.peek()))
postfix = postfix + " " + operators.pop();
operators.push(symbol);
}
}
}
while (!operators.isEmpty())
postfix = postfix + " " + operators.pop();
return postfix.trim();
}
static int prec(char x) {
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/' || x == '%')
return 2;
return 0;
}
}
class EvaluateString {
public static int evaluate(String expression) {
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
LinkedList<Integer> values = new LinkedList<Integer>();
// Stack for Operators: 'ops'
LinkedList<Character> ops = new LinkedList<Character>();
for (int i = 0; i < tokens.length; i++) {
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
// Current token is a number, push it to stack for numbers
if (tokens[i] >= '0' && tokens[i] <= '9') {
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0'
&& tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
ops.push(tokens[i]);
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')') {
while (ops.peek() != '(')
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
ops.pop();
}
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*'
|| tokens[i] == '/') {
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.isEmpty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.isEmpty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Top of 'values' contains result, return it
return values.pop();
}
// Returns true if 'op2' has higher or same precedence as 'op1',
// otherwise returns false.
public static boolean hasPrecedence(char op1, char op2) {
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
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;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.