package unl.cse.stacks; import java.util.Arrays; import java.util.HashSet; impor
ID: 3569215 • Letter: P
Question
package unl.cse.stacks;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class PostfixEvaluator {
private static final Set OPERATORS = new HashSet(Arrays.asList("+", "-", "*", "/"));
private final Stack stack;
/**
* Constructor
*/
public PostfixEvaluator() {
this.stack = new Stack();
}
private boolean isOperator(String s){
return OPERATORS.contains(s);
}
private String evaluate(String a, String b, String op) {
Double d1 = Double.parseDouble(a);
Double d2 = Double.parseDouble(b);
if(op.equals("+"))
return new Double(d1+d2).toString();
else if(op.equals("-"))
return new Double(d1-d2).toString();
else if(op.equals("*"))
return new Double(d1*d2).toString();
else if(op.equals("/"))
return new Double(d1/d2).toString();
else
throw new IllegalStateException("Unrecognized operator: "+op);
}
/**
* Evaluates the given arithmetic expression in postfix format
* change this method
* @param expression
* @return
*/
private double evaluateExpression(String expression) {
String values[] = expression.split("\s+");
for(String v : values) {
/*
* TODO: implement this method
* Hint:
* If v is an operator:
* pop b, a off the stack and call this.evaluate
* push the result back onto the top of the stack
* Else
* push the operand (number) onto the stack
*/
}
//At this point, the final result should be on the top of the stack,
//we pop it off, parse it and return the result
Double d = Double.parseDouble(this.stack.pop());
return d;
}
/**
*
* @param args
*/
public static void main(String[] args) {
PostfixEvaluator postfixEvaluator = new PostfixEvaluator();
System.out.print("Please enter the Arithmatic Expression (Postfix form) to evaluate: ");
Scanner myScanner = new Scanner(System.in);
String expression = myScanner.nextLine();
System.out.println(expression);
System.out.println("Result: " + postfixEvaluator.evaluateExpression(expression));
}
}
package unl.cse.stacks;
import unl.cse.linked_list.LinkedList;
public class Stack {
private final LinkedList list = new LinkedList();
public T pop() {
//TODO: implement this method
return null;
}
public void push(T item) {
//TODO: implement this method
}
public int size() {
//TODO: implement this method
return -1;
}
public boolean isEmpty() {
//TODO: implement this method
return false;
}
}
package unl.cse.linked_list;
import java.util.Iterator;
public class LinkedList implements Iterable {
private Node head = null;
private Node tail = null;
public void addElementToHead(T item) {
if(item == null)
throw new IllegalArgumentException("This LinkedList impelmentation does not allow null elements");
Node newHead = new Node(item);
if(this.tail == null) {
this.head = newHead;
this.tail = newHead;
} else {
newHead.setNext(this.head);
this.head.setPrevious(newHead);
this.head = newHead;
}
}
public T removeElementFromHead() {
T item = null;
if(this.size() == 0) {
throw new IllegalStateException("Cannot remove from an empty list");
} else if(this.size() == 1) {
item = this.head.getItem();
this.head = null;
this.tail = null;
} else {
item = this.head.getItem();
this.head = this.head.getNext();
this.head.setPrevious(null);
}
return item;
}
/**
* Returns the element at the head of this list, but does not remove it.
* @return
*/
public T getElementFromHead() {
if(this.size() == 0) {
throw new IllegalStateException("Cannot retrieve from an empty list");
} else {
return this.head.getItem();
}
}
public void addElementToTail(T item) {
if(item == null)
throw new IllegalArgumentException("This LinkedList impelmentation does not allow null elements");
Node newTail = new Node(item);
if(this.tail == null) {
this.tail = newTail;
this.head = newTail;
} else {
newTail.setPrevious(this.tail);
this.tail.setNext(newTail);
this.tail = newTail;
}
}
public T removeElementFromTail() {
T item = null;
if(this.size() == 0) {
throw new IllegalStateException("Cannot remove from an empty list");
} else if(this.size() == 1) {
item = this.tail.getItem();
this.head = null;
this.tail = null;
} else {
item = this.tail.getItem();
this.tail = this.tail.getPrevious();
this.tail.setNext(null);
}
return item;
}
/**
* Returns the element at the tail of this list, but does not remove it.
* @return
*/
public T getElementFromTail() {
if(this.size() == 0) {
throw new IllegalStateException("Cannot retrieve from an empty list");
} else {
return this.tail.getItem();
}
}
public int size() {
int count = 0;
for(T item : this) {
count++;
}
return count;
}
public boolean isEmpty() {
return (head == null);
}
@Override
public Iterator iterator() {
return new Iterator() {
Node curr = head;
@Override
public boolean hasNext() {
if(curr == null)
return false;
else
return true;
}
@Override
public T next() {
T item = curr.getItem();
curr = curr.getNext();
return item;
}
@Override
public void remove() {
throw new UnsupportedOperationException("not implemented");
}};
}
@Override
public String toString() {
if(this.head == null) {
return "[empty]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
Node curr = head;
while(curr != null) {
sb.append(curr.getItem());
if(curr.getNext() != null)
sb.append(", ");
curr = curr.getNext();
}
sb.append("]");
return sb.toString();
}
public static void main(String args[]) {
LinkedList llist = new LinkedList();
llist.addElementToHead(10);
llist.addElementToHead(20);
llist.addElementToTail(-10);
llist.addElementToTail(-20);
System.out.println(llist);
System.out.println(llist.removeElementFromHead());
System.out.println(llist.removeElementFromTail());
System.out.println(llist);
llist.addElementToTail(-50);
llist.addElementToTail(-60);
System.out.println(llist);
System.out.println(llist.isEmpty());
System.out.println(llist.removeElementFromTail());
System.out.println(llist.removeElementFromTail());
System.out.println(llist.removeElementFromTail());
System.out.println(llist.removeElementFromTail());
System.out.println(llist.isEmpty());
llist.addElementToTail(-50);
llist.addElementToTail(-60);
System.out.println(llist);
}
}
Explanation / Answer
Note:
Please note that the program which is provided did not contain a node class. The linked list class should be of template T type so that it can accept any type of data to compute.
Depending on the Linked list class, Stack class can be defined.
The code below is provide for evaluate expression is by using a inbuilt Stack class.
Program Code:
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
public class PostfixEvaluator {
private static final Set OPERATORS = new HashSet(Arrays.asList("+", "-", "*", "/"));
private final Stack stack;
/**
* Constructor
*/
public PostfixEvaluator() {
this.stack = new Stack();
}
private boolean isOperator(String s){
return OPERATORS.contains(s);
}
private String evaluate(String a, String b, String op) {
Double d1 = Double.parseDouble(a);
Double d2 = Double.parseDouble(b);
if(op.equals("+"))
return new Double(d1+d2).toString();
else if(op.equals("-"))
return new Double(d1-d2).toString();
else if(op.equals("*"))
return new Double(d1*d2).toString();
else if(op.equals("/"))
return new Double(d1/d2).toString();
else
throw new IllegalStateException("Unrecognized operator: "+op);
}
/**
* Evaluates the given arithmetic expression in postfix format
* change this method
* @param expression
* @return
*/
private double evaluateExpression(String expression) {
boolean lastCharIsDigit = false;
Stack<Integer> S = new Stack<Integer>();
for(int k = 0; k < expression.length(); k++)
{
char c =expression.charAt(k);
if( c >= '0' && c<= '9')
{
if(lastCharIsDigit)
{
S.push(S.pop()*10 + c-'0');
}
else
{
S.push( c - '0');
}
lastCharIsDigit = true;
}
else if (c == '+' || c== '-' || c == '*' || c == '/' || c == '%' || c == '~')
{
lastCharIsDigit = false;
if(S.isEmpty()) throw new RuntimeException("Empty Stack");
int RightOp = S.pop();
if( c == '~') S.push(-RightOp);
if(S.isEmpty()) throw new RuntimeException("Empty Stack.");
switch (c)
{
case '+' : S.push(S.pop() + RightOp); break;
case '-' : S.push(S.pop() - RightOp); break;
case '*' : S.push(S.pop() * RightOp); break;
case '/' : S.push(S.pop() / RightOp); break;
case '%' : S.push(S.pop() % RightOp); break;
}// END of switch
}
else if(c == ' ')
{
lastCharIsDigit = false;
}
else if ( c != ' ')throw new RuntimeException("Error!");
}
return S.pop();
}
/**
*
* @param args
*/
public static void main(String[] args) {
PostfixEvaluator postfixEvaluator = new PostfixEvaluator();
System.out.print("Please enter the Arithmatic Expression (Postfix form) to evaluate: ");
Scanner myScanner = new Scanner(System.in);
String expression = myScanner.nextLine();
System.out.println(expression);
System.out.println("Result: " + postfixEvaluator.evaluateExpression(expression));
}
}
---------------------------------------------------------------------------------------------------------------------------
Sample output:
At the output please provide the following format type
// String s = " 5 3 * 5 +"; // answer result =20
Please enter the Arithmatic Expression (Postfix form) to evaluate: 5 5 + 5 +
5 5 + 5 +
Result: 15.0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.