Application of Stack

Note:

You should use the Stack implementation. Its up to you whether you want to use Array-based or linked list based. Dont use predefined Stack available in Java. You can use class code after citing.

Q1. Brackets matching The Delimiters on the Stack (5 marks)

Write a java program that determines whether the given set of delimiters (in our case, it will be parenthesis such as ( and ) ) is validate or not.

Input:

Your program should read the input set of parenthesis from the user.

Output:

You would write on the console whether a given set of parenthesis is valid or not.

Sample Run:

Enter a String: ()

This is valid

Another run:

Enter a String: )(

This is invalid

Another run:

Enter a String: (())

This is valid

Note: For question 2 and question 3, you can assume that all the expressions contains only single digits number. There will not be any parenthesis in the expression. The operator will be +, -, * and /.

Q2. Convert from Infix to Postfix (5 marks)

We write expression with an operator (+, -, * and /) places between the operands. This is called infix notation because operator is placed between the operands. In postfix notation, operator follows the two operands. For Example A + B becaosme AB+. Below table describe Infix expression to postfix expression.

Below table describe how we can convert an expression from infix to post. Infix: A + B C, Postfix: AB+C-

Now consider another example

Below are the input to postfix transition rules:

In the above table, < and >= symbols refers to the operator precedence. The opThis operator has just been read from the infix input, while opTop operator has just been popped off the stack

You can follow these transition rules in our first two table.

Write a java program that read an infix expression from the user (console), and convert that expression in the postfix expression.

Sample Run:

Enter infix: 2+3*4

Postfix is: 234*

Q3. Evaluating expression (4 marks)

Below algorithm describe the evaluating postfix expression

• If item read from postfix expression is an operand, then push that item onto the stack
• If item read from postfix expression is an operator, pop the top two operands from the stack and apply the operator to them. Push the result.

When you are done, pop the stack to obtain the answer.

Sample Run:

Enter Postfix: 57

Evaluates to 12

Submit electronically via D2L:

1. Your source code files. Your TA will run your program to verify that it works correctly. Make sure your Java program compiles and runs without issues.
2. For Q1, the main file name should be Q1_LastName_FirstName.java. Same pattern will be for Q2 and Q3.

Grading Rubric:

Reference:

Some of the contents of the assignment has been adapted from Data Structures and Algorithm in Java, 2^nd Edition by Robert Lafore

Other Source:

Following will be extra resources to read if you are interested. https://introcs.cs.princeton.edu/java/43stack/ https://eecs.wsu.edu/~nroy/courses/cpts122/labs/Infix2Postfix.pdf