(Java) Provide a complete implementation of class LinkedStack and test it (main
ID: 3795258 • Letter: #
Question
(Java) Provide a complete implementation of class LinkedStack and test it (main method) on the InfixToPostfix applcation (listed below).
package linkedstack;
import java.util.*;
import java.util.regex.*;
/**
* Translates an infix expression to a postfix expression.
* @author Koffman & Wolfgang
*/
public class InfixToPostfix {
// Nested Class
/** Class to report a syntax error. */
public static class SyntaxErrorException extends Exception {
/**
* Construct a SyntaxErrorException with the specified
* message.
* @param message The message
*/
SyntaxErrorException(String message) {
super(message);
}
}
// Data Fields
/** The operator stack */
LinkedStack operatorStack;
//private Stack<Character> operatorStack;
/** The operators */
private static final String OPERATORS = "-+*/";
/** The precedence of the operators, matches order in OPERATORS. */
private static final int[] PRECEDENCE = {1, 1, 2, 2};
/**
* The Pattern to extract tokens
* A token is either a string of digits (d+)
* or a JavaIdentifier
* or an operator
*/
private static final Pattern tokens =
Pattern.compile("\d+\.\d*|\d+|"
+ "\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*"
+ "|[" + OPERATORS + "]");
/** The postfix string */
private StringBuilder postfix;
/**
* Convert a string from infix to postfix.
* @param infix The infix expression
* @throws SyntaxErrorException
*/
public String convert(String infix) throws SyntaxErrorException {
operatorStack = new LinkedStack();
postfix = new StringBuilder();
Scanner s = new Scanner(infix);
try {
// Process each token in the infix string.
String nextToken = null;
while ((nextToken = s.findInLine(tokens)) != null) {
char firstChar = nextToken.charAt(0);
// Is it an operand?
if (Character.isJavaIdentifierStart(firstChar)
|| Character.isDigit(firstChar)) {
postfix.append(nextToken);
postfix.append(' ');
} // Is it an operator?
else if (isOperator(firstChar)) {
processOperator(firstChar);
} else {
throw new SyntaxErrorException
("Unexpected Character Encountered: " + firstChar);
}
} // End while.
// Pop any remaining operators and
// append them to postfix.
while (!operatorStack.empty()) {
char op = (char) operatorStack.pop();
postfix.append(op);
postfix.append(' ');
}
// assert: Stack is empty, return result.
return postfix.toString();
} catch (EmptyStackException ex) {
throw new SyntaxErrorException("Syntax Error: The stack is empty");
}
}
/**
* Method to process operators.
* @param op The operator
* @throws EmptyStackException
*/
private void processOperator(char op) {
if (operatorStack.empty()) {
operatorStack.push(op);
} else {
// Peek the operator stack and
// let topOp be top operator.
char topOp = (char) operatorStack.peek();
if (precedence(op) > precedence(topOp)) {
operatorStack.push(op);
} else {
// Pop all stacked operators with equal
// or higher precedence than op.
while (!operatorStack.empty()
&& precedence(op) <= precedence(topOp)) {
operatorStack.pop();
postfix.append(topOp);
postfix.append(' ');
if (!operatorStack.empty()) {
// Reset topOp.
topOp = (char) operatorStack.peek();
}
}
// assert: Operator stack is empty or
// current operator precedence >
// top of stack operator precedence.
operatorStack.push(op);
}
}
}
/**
* Determine whether a character is an operator.
* @param ch The character to be tested
* @return true if ch is an operator
*/
private boolean isOperator(char ch) {
return OPERATORS.indexOf(ch) != -1;
}
/**
* Determine the precedence of an operator.
* @param op The operator
* @return the precedence
*/
private int precedence(char op) {
return PRECEDENCE[OPERATORS.indexOf(op)];
}
}
Explanation / Answer
import java.util.EmptyStackException;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.regex.Pattern;
class InfixToPostfixDemo {
private static final String OPERATORS = "-+*/";
private static final int[] PRECEDENCE = {1, 1, 2, 2};
private static final Pattern tokens = Pattern.compile("\d+\.\d*|\d+|" + "\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*" + "|[" + OPERATORS + "]");
java.util.Stack<Character> operatorStack = new java.util.Stack<Character>();
private static class SyntaxErrorException extends Exception {
public SyntaxErrorException(String message) {
super(message);
}
}
public String convert(String infix) throws SyntaxErrorException {
infix = "(" + infix + ")"; // enclose infix expr within parentheses
StringBuilder postfix = new StringBuilder();
try {
/* scan the infix char-by-char until end of string is reached */
for (int i = 0; i < infix.length(); i++) {
char firstChar, item;
firstChar = infix.charAt(i);
if (isOperand(firstChar)) // if(firstChar is an operand), then
{
postfix.append(firstChar); // append firstChar to postfix string 38 Lab Manual Data Structures through Java
} else if (firstChar == '(') // if(firstChar is a left-bracket), then
{
operatorStack.push(firstChar); // push onto the stack
} else if (isOperator(firstChar)) // if(firstChar is an operator), then
{
item = operatorStack.pop(); // pop an item from the stack
/* if(item is an operator), then check the precedence of firstChar and item*/
if (isOperator(item)) {
if (precedence(item) >= precedence(firstChar)) {
operatorStack.push(item);
operatorStack.push(firstChar);
} else {
postfix.append(item);
operatorStack.push(firstChar);
}
} else {
operatorStack.push(item);
operatorStack.push(firstChar);
}
} // end of if(isOperator(firstChar))
else if (firstChar == ')') {
item = operatorStack.pop();
while (item != '(') {
postfix.append(item);
item = operatorStack.pop();
}
} else {
throw new SyntaxErrorException("Unexpected Character Encountered: " + firstChar);
}
} // end of for-loop
// Pop any remaining operators and
// append them to postfix.
while (!operatorStack.empty()) {
char op = (char) operatorStack.pop();
postfix.append(op);
postfix.append(' ');
}
} catch (EmptyStackException ex) {
throw new SyntaxErrorException("Syntax Error: The stack is empty");
}
return postfix.toString();
} // end of toPostfix() method
public boolean isOperand(char c) {
return (c >= 'A' && c <= 'Z');
}
public boolean isOperator(char ch) {
return OPERATORS.indexOf(ch) != -1;
}
public int precedence(char op) {
return PRECEDENCE[OPERATORS.indexOf(op)];
}
public static void main(String args[]) {
InfixToPostfixDemo obj = new InfixToPostfixDemo();
String infix = "A*(B+C/D)-E";
System.out.println("infix: " + infix);
try {
System.out.println("postfix:" + obj.convert(infix));
} catch (SyntaxErrorException ex) {
Logger.getLogger(InfixToPostfixDemo.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.