Minimal Submitted Files You are required, but not limited, to turn in the follow
ID: 3762106 • Letter: M
Question
Minimal Submitted Files
You are required, but not limited, to turn in the following source files:
Assignment11.java(Complete, just use it for this assignment)
InfixToPostfixConverter.java (More codes need to be added)
Requirements to get full credits in Documentation
The assignment number, your name, StudentID, Lecture number/time, and a class description need to be included at the top of each file/class.
A description of each method is also needed.
Some additional comments inside of methods(especially for the "main" method) to explain code that are hard to follow should be written.
You can look at the Java programs in the text book to see how comments are added to programs.
Skills to be Applied
In addition to what has been covered in previous assignments, the use of the following items, discussed in class, will probably be needed:
java.util.Stack
Program Description
In this assignment, you're required to write a program to convert an infix notation to its corresponding postfix notiation by using the Stack data structure.
In arithmatics, the infix notation is like (A+B)*C, where the operators, + and *, are written between the operand, A, B and C. The corresponding postfix notation is AB+C*, where the operators follow the operands. Postfix notation has the advantage that:
It does not require parentheses
The operators appear in the order required for computation
Below please find the algorithm that converts an infix notation to a postfix notation
1. Initialise an empty stack.
2. Scan the Infix string from left to right, one charater at a time, depends on which character you have, there are several cases here:
Case A: If the scannned character is an operand, add it to the Postfix string.
Case B: If the scanned character is a left parenthesis, just push it on top of the stack.
Case C: If the scanned character is an operator and the stack is empty, push the character on top of the stack.
Case D: If the scanned character is an operator and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character, Pop the stack and append it to Postfix string, else push the scanned character on top of the stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
Case E: If the scanned character is a right parenthesis and the stack is not empty, pop everything out from the stack and append them one by one to Postfix string until we encounter the first left parenthesis on stack, then stop. (Note: the first encountered left parenthesis on stack will be pop out and discarded). If there's no left parenthesis to match the right parenthesis, return a "No matching open parenthesis error" as output.
3. Repeat above steps until all the characters in infix notation are scanned.
4. Case F: After all characters in infix notation are scanned, we then check the contents of the stack. If topStack is a left parenthesis, return a "No matching close parenthesis error" string as output and stop. If the stack is not empty and topStack is not a left parenthesis, we pop it out and append it to the Postfix string. Repeat this step as long as stack is not empty. In other words, we have to add any characters other than the left parenthesis that the stack may have to the Postfix string.
5. Return the Postfix string.
Click here to see a sample showing above algorithm.
Note:
(1) Just assume the Infix strings are simple arithemetic expression with +, -, *, / as operators only. And * , / have higher precedence over +, -.
(2) Assume the operhand are only letters, both upper or lower cases, such as A, B, C, ..., Z or a, b, c, ....z
(3) Since java.util.Stack class only accept objects, you can use methods valueOf( ) and charValue( ) in wrapper class Character to do boxing and unboxing. For example:
Character charObj = Character.valueOf( 'A');
char sampleChar = ( (Character) sampleStack.pop( )).charValue( );
(4) Put comments to mark each cases clearly inside your code.
-----------------------------------------------------------------------------------------------------------------------------
// Description: Assignment 11 class displays a menu of choices to a user
// and performs the chosen task. It will keep asking a user to
// enter the next choice until the choice of 'Q' (Quit) is entered.
import java.io.*;
public class Assignment11
{
public static void main (String[] args)
{
char input1;
String inputInfo;
String line = new String();
printMenu();
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader stdin = new BufferedReader(isr);
do // will ask for user input
{
System.out.print("What action would you like to perform? ");
line = stdin.readLine();
input1 = line.charAt(0);
input1 = Character.toUpperCase(input1);
if (line.length() == 1)
{
// matches one of the case statements
switch (input1)
{
case 'E': //Enter String
System.out.print("Please enter a string. ");
inputInfo = stdin.readLine().trim();
System.out.print(InfixToPostfixConverter.convertToPostfix(inputInfo)+" ");
break;
case 'Q': //Quit
break;
case '?': //Display Menu
printMenu();
break;
default:
System.out.print("Unknown action ");
break;
}
}
else
{
System.out.print("Unknown action ");
}
} while (input1 != 'Q' || line.length() != 1);
}
/** The method printMenu displays the menu to a user**/
public static void printMenu()
{
System.out.print("Choice Action " +
"------ ------ " +
"E Enter String " +
"Q Quit " +
"? Display Help ");
}
}
--------------------------------------------------------------------------------------------------------------------------------------------
// Description: This is a utility class that provide a static method that
// takes an infix string, checked and determine if parentheses
// are matching, if matching, returns a postfix string.
import java.util.Stack;
public class InfixToPostfixConverter
{
//**********************************************************************
//The precedence method determines the precedence between two operators.
//If the first operator is of higher or equal precedence than the second
//operator, it returns the value true, otherwise it returns false.
//***********************************************************************
public static boolean precedence(char first, char second)
{
}
//*************************************************************************
//The static convertToPostfix method will convert the infixString
//into the corresponding postfix string. Check the algorithm on
//assignment #11's description page. Mark each case clearly inside the code
//*************************************************************************
public static String convertToPostfix(String infixString)
{
//initialize the resulting postfix string
String postfixString = "";
//initialize the stack
Stack<Character> stack1 = new Stack<Character>();
//Obtain the character at index i in the string
for (int i=0; i < infixString.length(); i++)
{
char currentChar = infixString.charAt(i);
//Case A:
//Case B:
//Case C:
//Case D:
//Case E:
} //end of for loop
//Case F:
}//end of convertToPostfix method
}//end of the InfixToPostfixConverter class
Explanation / Answer
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;
public class Assignment11 {
public static void main(String[] args) throws FileNotFoundException {
//Test 1:
//enter an expression in Infix : 1 * ( 12 + 23 ) - ( 4 / 5 )
//PostFix form : 1 12 23 + * 4 5 / -
//Test 2:
//enter an expression in Infix : 100 * ( 2 + 12 )
//PostFix form :100 2 12 + *
File file = new File("infixexp.txt");
Scanner scanner = new Scanner(file);
int i=1;
while(scanner.hasNext()){
System.out.println("Expression "+i++);
String infix = scanner.nextLine();
System.out.println("inFix form :"+infix);
String postfix = convert(infix);
System.out.println("PostFix form :"+postfix);
int result=evaluatePostfix(postfix.split(" "));
System.out.println("postFix Expression Evaluation : "+result);
}
}
public static int evaluatePostfix(String[] expr) {
Stack<Integer> nums = new Stack<Integer>();
for(int i = 0; i < expr.length; i++) {
String elt = expr[i];
if(elt.equals("+")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a + b));
} else if(elt.equals("-")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a - b));
} else if(elt.equals("*")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a * b));
} else if(elt.equals("/")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a / b));
}else if(elt.equals("^")) {
int b = nums.pop().intValue();
int a = nums.pop().intValue();
nums.push(new Integer(a ^ b));
} else { // it must be a number
int x = Integer.parseInt(elt);
nums.push(new Integer(x));
}
}
return nums.pop().intValue();
}
/**
* Perform the conversion
*
* @param expression Arithmetic infix format
*/
public static String convert(String expression) {
// Use StringBuilder to append string is faster than
// String concatenation
StringBuilder sb = new StringBuilder();
// Use a stack to track operations
Stack<Character> op = new Stack<Character>();
// Convert expression string to char array
char[] chars = expression.toCharArray();
// The length of expression character
int N = chars.length;
for (int i = 0; i < N; i++) {
char ch = chars[i];
if (Character.isDigit(ch)) {
// Number, simply append to the result
while (Character.isDigit(chars[i])) {
sb.append(chars[i++]);
}
// Use space as delimiter
sb.append(' ');
} else if (ch == '(') {
// Left parenthesis, push to the stack
op.push(ch);
} else if (ch == ')') {
// Right parenthesis, pop and append to the result until meet the left parenthesis
while (op.peek() != '(') {
sb.append(op.pop()).append(' ');
}
// Don't forget to pop the left parenthesis out
op.pop();
} else if (isOperator(ch)) {
// Operator, pop out all higher priority operators first and then push it to the stack
while (!op.isEmpty() && priority(op.peek()) >= priority(ch)) {
sb.append(op.pop()).append(' ');
}
op.push(ch);
}
}
// Finally pop out whatever left in the stack and append to the result
while(!op.isEmpty()) {
sb.append(op.pop()).append(' ');
}
System.out.println("sb=="+sb);
return sb.toString();
}
/**
* Check if a character is an operator
*/
private static boolean isOperator(char ch) {
return ch == '^' || ch == '*' || ch == '/' || ch == '+' || ch == '-';
}
/**
* Define the operator priority
*/
private static int priority(char operator) {
switch (operator) {
case '^' : return 3;
case '*' :
case '/' : return 2;
case '+' :
case '-' : return 1;
}
return 0;
}
}