TK1143 Program Design, Session 20222023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
TK1143 Program Design
STACK & QUEUE
Section A:
1. Write a java statement to declare and create:
a) A stack object called myNumber that will be assigned with decimal values.
b) A queue object called author from the BOOK class.
2. What is the output of the following program. Draw the content of myStack.
3. What the output of the following program and draw the content of vChar queue.
Section B:
1. Trace and write the output of the following program using the sample input given. Explain the implementation of stack in this program.
Sampel Input
2
i like to eat chocolate #
java programming #
2. Trace and write the output of the following java program. Explain the implementation of queue in this program.
3. Palindrome is a sequence of characters, a word, phrase, number or sequence of words which reads the same backward as forward. Example of palindrome words are katak, civic and anna. Write a java code to identify ifthe input word is palindrome using data structure.
Example Input |
Example Output |
racecar java madam |
It is a Palindrome Not a palindrome It is a Palindrome |
a) List all possible data structure that can be used to solve the Palindrome problem
b) Explain how these data structure can identify if the input is palindrome?
c) Write a program to determine if a word is a palindrome.
4. Refer to the full structure of the work Example program: ABC Wash Machine Simulation on pages 17 and 18 from Queue Reading Material.
Complete the following:
a) Line 29 is a method to _______________________________________________________.
b) What are the numbers that will be generated from the code in Line 35? ______________
c) The object declaration from class Clock in Line 19-25 hold _________________________.
_________________________________________________________________________
d) Class Clock consist of 3 data member of type integer, which are __________________.
e) Why the code in Line31 pass value (8,0,0) as parameter to object startTime?
__________________________________________________________________________ .
f) Why the code in Line32 pass value (8,30,0) as parameter to object endTime?
_________________________________________________________________________ .
What is the function of code in Line36?
_________________________________________________________________________.
_________________________________________________________________________
g) What is the last arrival time for the last car that the machine will accept if the program generates nextArrival values as follows: __________________________.
Section C:
This section hasfive questions but you need to answerfour questions (2 stack 2 queue). Discuss self-study in exercises and assignment questions with your class instructor. For the topic stack, there are two assignment questions but you are required to answer only one.
POSTFIX MACHINE (P) |
|
Input |
Standard Input |
Output |
Standard Output |
Java Elements |
Loop, Selection |
Data Structure |
Stack |
Problem Description
The Postfix Machine is a program that receives a postfix expression and calculates the value of the expression. The postfix form represents a natural way to evaluate expressions because precedence rules are not required. The black box shown below represents the Postfix Machine. If we give the input 4 2 3 * +, the program will give the output 10. How is the evaluation done?
The evaluation is done as follows:
4 2 3 * + [ Compute the last two operands with the first operator that is 2 * 3]
4 6 + [ Repeat the computation]
10 [ This is the result]
Scope of the program:
● The operator is a binary operator: addition, multiplication, division, and subtraction.
● The operand is not more than 3-digit integer.
● The expression ends with symbol semicolon.
● The expression only contains operand, operator and semicolon that are separated by spaces.
Your task is to write a program for postfix machine with implementing Stack .
Input
The input contains only symbol +, -, *, / and positive number with not more than 3 digits. Each of the symbol and numbers are separated with a single space. The input ends with symbol semicolon.
Input example:
4 2 3 * + ;
120 3 4 * - 5 + ;
4 2 3 * +
Output
The output will be an integer. Based on the above example, the output will be:
10
113
ERROR: no END OF STRING in the expression
Solution
Postfix Machine Algorithm:
Read the string
Split the string into tokens
Repeat until token is semicolon
When a binary operator is seen: the two operands are popped from the stack, the operator is evaluated, and the result is pushed back onto the stack. When an operand is seen: it is pushed onto a stack. |
Read next token
When the complete postfix expression is evaluated: the result should be a single item on the stack |
Basic Structure of the program:
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Stack myStack = new Stack();
String InStr;
InStr = in.nextLine();// input string
StringTokenizer st = new StringTokenizer(InStr);
while (st.hasMoreTokens()) {
String nextT = st.nextToken();
if(!(nextT.equals(";"))) {
PART A1 |
}
else
break;
}
}
Complete structure of the program/solution: PostfixMachine.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
import java.util.*; public class PostfixMachine { public static void main(String[] args) { Scanner in = new Scanner(System.in); Stack myStack = new Stack(); String InStr; Integer f1, f2; int result; InStr = in.nextLine(); // input string StringTokenizer st = new StringTokenizer(InStr); while (st.hasMoreTokens()) { String nextT = st.nextToken(); if(!(nextT.equals(";"))) { if (isOperator(nextT)){ // // >>> ADD YOUR CODE I HERE <<< } else { // >>> ADD YOUR CODE II HERE <<< } } else break; } // >>> ADD YOUR CODE III HERE <<< } // end main() static boolean isOperator(String tmp) { if ((tmp.equals("+")) | |(tmp.equals("-")) | |(tmp.equals("*")) | | (tmp.equals("/"))) return true; return false; } static int evaluate(Integer op1, Integer op2, String s1) { int data1 = op2.</ |
2023-06-02