'java right to left evaluator turning into a left to right evaluator, StringIndexOutOfBoundsException java
I have an assignment where I need to transform a right to left evaluator program into a left to right evaluator program(also make it so where it asks you to evaluate multiple expressions with a Y/N prompt). there were several changes I needed to make to the program such as
- permit spaces between numbers and operators
- a negative number should have a minus sign followed immediately by a digit or a decimal point; further, negative numbers should usually be surrounded by parentheses. (this is different from the old program which uses underscores for negatives)
- Exponentiation should be permitted, with the highest precedence.
- Evaluation should be left to right. This is the main change.A) The formNum() method has to be rewritten so that it scans from left to right when it encounters the leftmost digit of a number or a leading decimal point. Of course, the method of building up the double value from the successive digits has to be adjusted since you are scanning from left to right- try some examples to discover the correct approach. B) The evaluator() method also has to be adjusted to scan from left to right. There are several changes: i) When a left parenthesis is encountered it is always pushed onto stack A unless it signals a negative number (as in 5+ (-13.4) +2). In that case, formNum() should be called to compute the negative number and push it as a double onto B, and the corresponding right parenthesis should be skipped over. ii) When a right parenthesis is encountered (but not the right end of a negative number) it triggers a call to evalDown() to evaluate the operations in a parenthesized subexpression until the corresponding left parenthesis is reached. The left parenthesis is also popped from A. iii) when the current token operator is equal in precedence to the operator at the top of the stack, do not push the token. Instead, perform the operation at the top of the A stack using eval(), and then compare the current token operator to the new top of the A stack. Example. Suppose we have 3.0 / 2.0 * 4.0 . We push 3 onto B , / onto A, and 2 onto B. If we (incorrectly) push * onto A (it has equal precedence with /), and then 4 onto B, we will compute 2 * 4 first and then 3/8.. Instead, we should compute 3./2 first and push 1.5, and later compute 1.5 * 4 = 6.0. (In right to left scanning, we always pushed the new operator if it had equal precedence with the top operator, now we do not push it.) iv) push a new token operator or left parenthesis (except one indicating a negative number) on top of a left parenthesis at the top of stack A.
with this in mind here are the old program files //i have put the old programs files in a pastebin link to make readability a bit easier.
ExpresionEvaluator.java https://pastebin.com/QkKdU6dh
ExprEvaluatorTest.java https://pastebin.com/3UqqLsvr
Stack1gen.java https://pastebin.com/KW4Pz9Pt
and here are my attempts at the new program.
LR.java
import java.util.Scanner;
//class for evaluating arithmetic expressions as double values, which are displayed rounded to 7 places,
//with decimal points supressed for whole numbers. The unrounded double value is returned.
public class LR
{
Scanner kb = new Scanner(System.in); //allaws spaces
//class-wide variables:
//Since expressions are evaluated one at a time, all evaluations can use the same two stacks.
private static Stack1gen<Character> A = new Stack1gen<Character>(); //stack for operators
private static Stack1gen<Double> B = new Stack1gen<Double>(); //stack for operands
//class-wide methods:
//method to print a double value that is an integer as an int
public static void expressionOutput(double x)
{
if(x == (double)Math.round(x)) //if the answer is a whole number,
//display without decimal point
{
int intAns = (int)x;
System.out.println("value = " + intAns + '\n');
}
else
{
System.out.println("value = " + x + '\n');
}
}
/*Expressions are evaluated from right to left, using a stack A of arithmetic
operators and a stack B of operands. In this method, a single operation is
evaluated by popping the current operator from A, its 2 operands from B, and by then
performing the operation and pushing the result onto B as a double value.*/
private static void eval()
{
char op = A.pop(); //current operator
double opnd1 = B.pop(); //operands
double opnd2 = B.pop();
double val = 0.0;
switch (op) //evaluate
{
case '+':
val = opnd1 + opnd2;
break;
case '-':
val = opnd1 - opnd2;
break;
case '*':
val = opnd1 * opnd2;
break;
case '/':
val = opnd1/opnd2;
break;
case '^':
val = Math.pow(opnd1, opnd2); //update: allow for exponation
break;
}
B.push(val); //push result onto B
}
/* In this method, a parenthesized subexpression is
evaluated by evaluating its operations on Stack A top-down
until a right parenthesis is encountered on stack A;
the right parenthesis is also popped from A*/
private static void evalDown()
{
do
{
eval();
}while((A.getSize()>0) && (A.getTop() != ')'));
if((A.getSize()>0) && (A.getTop() == ')'))
{
A.pop();
}
}
//This method compares the current operator token in the input string to the operator
//on top of stack A to determine precedence.
private static boolean prec(char token, Stack1gen<Character> StackA)
{
char topOp = StackA.getTop();
if(token == '^'){// update:exponents take max prec
return true;
}
else if((token == '*') || (token == '/'))
{
return true; //token has precedence, so it will be pushed onto A
}
else
{
if((topOp == '*') || (topOp == '/'))
{
return false; //operator at top of A has precedence
}
else
{
return true; //equal low-precedence operators or token is ')',
// which is always pushed onto A
}
}
}
//variables for an ExprEvaluator object
private String e;
private int p; //pointer to characters within the expression string e
//constructor
public LR()
{
System.out.println("enter an expression");
e = kb.nextLine(); //input an arithmetic expression as a line of keyboard input.
e = e.replaceAll(" ", ""); // Update: gets rid of all spaces from input, allowing spaces in input.
p = e.length()-1;
}
//parameterized constructor
public LR(String ee)
{
e = ee;
p = ee.length() - 1;
}
public String getExpression()
{
return e;
}
//If a substring of e whose rightmost character is at position p
//represents a number (possibly with a decimal point, possibly negative),
//return the numerical value of the substring as a double value and
//re-position p just to the left of the substring.
private double formNum() // im not sure if i swaped the order corectly
{
double total = 0.0;
int count = 0;
int flag = 0;
double mult = 1.0;
char c,d;
do
{
c = e.charAt(p); //examine the current character in the string (from right to left)
if(c == '.')
{
flag = 1; //set a flag to remember that the character is a decimal point
}
else
{
//if the current character is a digit, convert to its
//int value and include it in the value corresponding to the string.
if((c >= '0') && (c<= '9'))
{
total = total + mult * (c-'0');
mult = mult * 10.0;
if(flag == 0)
{
count++; //count the number of digits to the right of a possible decimal point
}
}
else
{
if(c == '-' )
{
total = -total;
}
}
}
p++; //Prepare to move to the next character to the right.
//This is a private non-static method because it changes the member variable p
d = '?';
if(p<= 0)
{
d = e.charAt(p); //the next character to the right
}
}while((p>=0) && (((d<='9')&&(d>='0'))||(d=='-' && d-1 =='(')||(d=='.')));//check for a valid character //upate: uses - with a check is the previous char is ( // im not sure this is right
if(flag==1)
{
total = total/Math.pow(10.0,count*1.0); //compute the value taking into account
//the number of decimal places
}
return total;
}
//This method uses the 2-stack approach to evaluate an expression (from right to left).
//The result is rounded to 7 decimal places and displayed as explained in expressionOutput() above.
//The original double value (unrounded) is returned to the calling program.
//The code could be made more efficient (but more difficult to read) by using if-else-if-else...
//as in formNum(); here we (unnecessarily) execute each if statement.
public double evaluator()
{
char token; //current token in the input expression
//loop to scan the string right to left
do
{
// if right perentheses, evaluate and pop of that A stack
token = e.charAt(p);
if(token == ')')
{
if(token-1!='-'){
evalDown();
A.pop();
}
p++;
}
//if the token is a left parenthesis,
//A push
//else B push reults from form num
if(token == '(' )
{
if(token+1!='-'){
A.push(token);
}
else{
B.push(formNum());
}
p++; //move
}
//method that checks for higher prec
if((token=='+')||(token=='-')||(token=='*')||(token=='/')||(token=='^'))
{
if((A.getSize() == 0) || (prec(token, A) == true))
{
eval();
p++;
}
//If the token is an arithmetic operator of lower precedence than that
//at the top of the stack, then evaluate the operation at the top of stack A.
else
{
eval();
}
}
//if the token is the rightmost digit of a number or a decimal point on the right,
//form the number as a double and push onto stack B
if(((token<='9')&&(token>='0'))||(token=='.'))
{
B.push(formNum());
}
}while(p >= 0);//continue to scan from right to left
//after completely scanning the input string, evaluate any remaining operations
while(A.getSize()>0)
{
eval();
}
double x = B.pop();
//round the result to 7 places and then display
expressionOutput((double)Math.round(x*10000000)/10000000.0);
return x; //return the original double value
} //end of evaluator
} //end of class
LRTest.java
import java.util.Scanner;
/**
* This is a tester class for expresions
*
* I can not get this code to work so i am submitting what i have
*/
public class LRTest {
public static void main(String[] args) {
char choice;
try (Scanner kb = new Scanner(System.in)) {
System.out.println("would you like to enter a choice? Y/N");
choice = kb.next().charAt(0);
while ((choice == 'y') || (choice == 'Y')) {
System.out.println("Enter an expression.");
LR expr = new LR(kb.nextLine());
System.out.println(expr.getExpression() + '\n');
expr.evaluator(); // evaluate expr1
System.out.println("would you like to enter another experesion? Y/N");
choice = kb.next().charAt(0);
}
kb.close();
// do
// {
// // Get the choice from the user to add more number
// System.out.print(" Would you like to doo another expresion. Enter Y for yes
// or N for no: ");
// choice = kb.next().charAt(0);
// System.out.println("enter an expresion");
// LR expr = new LR( kb.nextLine());
// System.out.println(expr.getExpression() + '\n');
// expr.evaluator(); //evaluate expr1
// }
// while ((choice == 'y') || (choice == 'Y'));
// kb.close();
}
}
}
and Stack1gen.java // EDIT: accidently put wrong code for this class
//Stack1gen.java
//array implementation of stack class
public class Stack1gen<T>
{
int MAX = 30; //maximum number of stack entries
private int top;
private T[] stack; //array to hold the stack data
//default constructor
public Stack1gen()
{
top = MAX; //initialize an empty stack
stack = (T[]) new Object[MAX];
}
//copy constructor
// public Stack1(Stack1 s)
// {
// top = s.top;
// for(int i = top; i<=MAX-1; i++)
// {
// stack[i] = s.stack[i];
// }
// }
public void push(T y) //push data item y onto the stack
{
assert(top > 0); //check that there is room on the stack
top = top -1;
stack[top] = y;
}
public T pop() //pop the top item from the stack and return it
{
assert(top < MAX); //check that there is data on the stack
T x = stack[top];
top = top +1;
return x;
}
public int getSize()
{
return MAX-top;
}
public T getTop()
{
assert(top < MAX);
return stack[top];
}
// public void printStack() //print the contents of the stack, from
// top to bottom, one item per line, without popping the stack items.
}
when I run LRtest.java and type y I get a StringIndexOutOfBoundsException and it points to the beginning of evaluator() . I have no idea what is wrong. if anyone can help me that would be greatly appreciated.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|