Please submit the homework as Stack.java and InfixConverter.java on blackboard.
ID: 3803464 • Letter: P
Question
Please submit the homework as Stack.java and InfixConverter.java on blackboard. You are welcome to use the starter files provided on blackboard.
1 Problem 1 Implement a stack. You do not need to actually extend an interface I simply want you to implement a stack. I have given you a starte below: public class Stack { //You will need to have some sort of private variables to store the stack itself here. //If you use a linked implementation include the node in the submission. public Stack() { //Fill in your code here. } public void pop() { //Fill in your code here. } public T top() { //Fill in your code here. } public void push(T element) { //Fill in your code here. } //You are welcome to add any other private functions. } 1
2Problem 2 Write a program called InfixConverter.java that takes in a string from the command line containing an infix arithmetic expression including (,),+,-,* and the integers and outputs the postfix expression. We will discuss this algorithm in class so make sure to take good notes. It is similar to the case study in Section 3.8 (that allows you to evaluate the postfix expressions we are generating!). Make sure that this class uses the Stack you implemented in problem 1.
Example input: (2 + 3) * 4 - 2
Example Output 2 3 + 4 * 2 -
Explanation / Answer
a) IMPLEMENTING STACK:
This is a Java Program to implement a stack. Stack is an area of memory that holds all local variables and parameters used by any function and remembers the order in which functions are called so that function returns occur correctly. ‘push’ operation is used to add an element to stack and ‘pop’ operation is used to remove an element from stack. ‘peek’ operation is also implemented returning the value of the top element without removing it. The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. The implemented stack has bounded capacity.
Here is the source code of the Java program to implement a stack. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
b) INFIX TO POSTFIX:
import java.io.*; class stack { char stack1[]=new char[20]; int top; void push(char ch) { top++; stack1[top]=ch; } char pop() { char ch; ch=stack1[top]; top--; return ch; } int pre(char ch) { switch(ch) { case '-':return 1; case '+':return 1; case '*':return 2; case '/':return 2; } return 0; } boolean operator(char ch) { if(ch=='/'||ch=='*'||ch=='+'||ch=='-') return true; else return false; } boolean isAlpha(char ch) { if(ch>='a'&&ch<='z'||ch>='0'&&ch=='9') return true; else return false; } void postfix(String str) { char output[]=new char[str.length()]; char ch; int p=0,i; for(i=0;i<str.length();i++) { ch=str.charAt(i); if(ch=='(') { push(ch); } else if(isAlpha(ch)) { output[p++]=ch; } else if(operator(ch)) { if(stack1[top]==0||(pre(ch)>pre(stack1[top]))||stack1[top]=='(') { push(ch); } } else if(pre(ch)<=pre(stack1[top])) { output[p++]=pop(); push(ch); } else if(ch=='(') { while((ch=pop())!='(') { output[p++]=ch; } } } while(top!=0) { output[p++]=pop(); } for(int j=0;j<str.length();j++) { System.out.print(output[j]); } } } class intopost { public static void main(String[] args)throws Exception { String s; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); stack b=new stack(); System.out.println("Enter input string"); s=br.readLine(); System.out.println("Input String:"+s); System.out.println("Output String:"); b.postfix(s); } }