Need some help with the following methods: public static int eval(String s) A me

Question

Need some help with the following methods:

public static int eval(String s)
A method to completely evaluate a single expression in the form of a String.

public static void apply(GenStack<Integer> val, GenStack<Character> op)
A method to apply a single binary operation. This methods takes an operator from op along with two values from val and performs the operation. The result is pushed back onto val.

public static int prec(char op)
A method to determine operator precedence.

My project code so far:

import java.util.*;
import java.io.*;

public class Project {


public static void main(String[]args) throws FileNotFoundException{

GenStack<Character> op = new GenStack<Character>();
GenStack<Integer> val = new GenStack<Integer>();

}
public static void apply (GenStack<Integer> val, GenStack<Character> op){

}public static int eval(String s){

GenStack<String> op = new GenStack<String>();
GenStack<Integer> val = new GenStack<Integer>();


public static int prec (char c) {
switch (c) {
case '+':
case '-':
return(5);
case '*':
case '/':
case '%':
return(10);
case '(':
return(0);
} /* switch */
return (0);
} /* prec */

}

}

My GenStack code: (I think this is complete)

import java.util.*;

public class GenStack<T> {

private Node<T> top;

private class Node<T> {
private T data;
private Node<T> next;
private Node(T item) {
data = item;
next = null;
}
}
public GenStack () {
top = null;
}
public void dumplist() {
Node<T> p = top;
while ( p != null ) {
System.out.print(p.data + " ");
p = p .next; }
System.out.println();
}

public T pop() throws EmptyStackException {
if ( top == null )
throw new EmptyStackException();
T val = top.data;
top = top.next;
return val;
}

public T top() throws EmptyStackException {
if ( top == null )
throw new EmptyStackException();

return top.data;
}

public void push (T item) {

Node<T> n = new Node<T>(item);
n.next = top;
top= n;
}

public boolean isEmpty()
{
return top == null;
}

}

Input expression (( 50 + 40) / 2 ) + ( 2* ( 3 + 1))

Should output like (( 50 + 40) / 2 ) + ( 2* ( 3 + 1)) = 53

All expression evaluation will occur in the eval() method where you will have two stacks: an operator stack and a value stack.
Expressions will have the following components:
Integers
Binary Operators {*, /, %, +, -}.
Parentheses for altering precedence.
Whitespace which can be ignored.

Precedence rules are the same as for Java. Parentheses {(, )}first, then {*, /, %} and lastly {+, -}. Operators of like precedence are evaluated from left to right.
You should pass prec() the operator and have it return an integer. This is so you can compare the precedence of the operator on the stack with the one from the input stream.
Be certain to apply whatever is left on the value and operator stacks once the expression in its string form has been exhausted. The result will be the only value left on the value stack.

Consider the following evaluation rules:

The rules for evaluation of expressions are as follows:

(

push onto operator stack

value

push value onto value stack

)

while (top operator stack != '(')
apply
pop '(' from operator stack

operator

while (! empty operator stack && (prec(currop) <= prec(top operator stack)))
apply
push currop

end of string

while (! empty operator stack)
apply
result remains on value stack

Explanation / Answer

// infix.java
// converts infix arithmetic expressions to postfix
// to run this program: C>java InfixApp
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize;
private char[] stackArray;
private int top;
//--------------------------------------------------------------
public StackX(int s) // constructor
{
maxSize = s;
stackArray = new char[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(char j) // put item on top of stack
{ stackArray[++top] = j; }
//--------------------------------------------------------------
public char pop() // take item from top of stack
{ return stackArray[top--]; }
//--------------------------------------------------------------
public char peek() // peek at top of stack
{ return stackArray[top]; }
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{ return (top == -1); }
//-------------------------------------------------------------
public int size() // return size
{ return top+1; }
//--------------------------------------------------------------
public char peekN(int n) // return item at index n
{ return stackArray[n]; }
//--------------------------------------------------------------
public void displayStack(String s)
{
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for(int j=0; j<size(); j++)
{
System.out.print( peekN(j) );
System.out.print(' ');
}
System.out.println("");
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class InToPost // infix to postfix conversion
{
private StackX theStack;
private String input;
private String output = "";
//--------------------------------------------------------------
public InToPost(String in) // constructor
{
input = in;
int stackSize = input.length();
theStack = new StackX(stackSize);
}
//--------------------------------------------------------------
public String doTrans() // do translation to postfix
{
for(int j=0; j<input.length(); j++) // for each char
{
char ch = input.charAt(j); // get it
theStack.displayStack("For "+ch+" "); // *diagnostic*
switch(ch)
{
case '+': // it's + or -
case '-':
gotOper(ch, 1); // go pop operators
break; // (precedence 1)
case '*': // it's * or /
case '/':
gotOper(ch, 2); // go pop operators
break; // (precedence 2)
case '(': // it's a left paren
theStack.push(ch); // push it
break;
case ')': // it's a right paren
gotParen(ch); // go pop operators
break;
default: // must be an operand
output = output + ch; // write it to output
break;
} // end switch
} // end for
while( !theStack.isEmpty() ) // pop remaining opers
{
theStack.displayStack("While "); // *diagnostic*
output = output + theStack.pop(); // write to output
}
theStack.displayStack("End "); // *diagnostic*
return output; // return postfix
} // end doTrans()
//--------------------------------------------------------------
public void gotOper(char opThis, int prec1)
{ // got operator from input
while( !theStack.isEmpty() )
{
char opTop = theStack.pop();
if( opTop == '(' ) // if it's a '('
{
theStack.push(opTop); // restore '('
break;
}
else // it's an operator
{
int prec2; // precedence of new op

if(opTop=='+' || opTop=='-') // find new op prec
prec2 = 1; // assign top op prec for add op
else
prec2 = 2; // assign top op prec for other op
if(prec2 < prec1) // if prec of top op less
{ // than prec of incoming
theStack.push(opTop); // save newly-popped op
break;
}
else // prec of new not less
output = output + opTop; // than prec of old
} // end else (it's an operator)
} // end while
theStack.push(opThis); // push new operator
} // end gotOp()
//--------------------------------------------------------------
public void gotParen(char ch)
{ // got right paren from input
while( !theStack.isEmpty() )
{
char chx = theStack.pop();
if( chx == '(' ) // if popped '('
break; // we're done
else // if popped operator
output = output + chx; // output it
} // end while
} // end popOps()
//--------------------------------------------------------------
} // end class InToPost
////////////////////////////////////////////////////////////////
class InfixApp
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
System.out.print("Enter infix: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // quit if [Enter]
break;
// make a translator
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans(); // do the translation
System.out.println("Postfix is " + output + ' ');
} // end while
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
} // end class InfixApp
////////////////////////////////////////////////////////////////

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.