Implement a stack and solutions to the following problems: balancing parenthesis, evaluating postfix expressions and transforming infix expressions into postfix expressions.

Implement a stack and solutions to the following problems: balancing parenthesis, evaluating postfix expressions, and transforming infix expressions into postfix expressions. From the attached file i just need an 4 to be solved. I will provide the code template as well.

Data Structures and Algorithms
Assignment 2
Due: 2/19/2021 on Canvas
(100 points)
Total 4 questions. Instructions Submit your answers and code on Canvas. Include a brief README file
explaining your code, especially if you implemented some of the suggestions for extra credit.
Question 1 (20 points)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence ?(?) = 3?(?/3) +
?. Use the substitution method to verify your answer.
Question 2 (20 points)
Solve the following recurrences using the Master Theorem.
• ?(?) = 2?(?/4) + 1
• ?(?) = 2?(?/4) + √?
• ?(?) = 2?(?/4) + ?
• ?(?) = 2?(?/4) + ?
2
Question 3 (10 points)
Write a program void reverse_list(list **l)in pseudo-code or C++ to reverse the direction
of a given singly-linked list. In other words, after the reversal all pointers should now point backwards.
Your algorithm should take linear time. The node of this singly-linked list is defined as
typedef struct list {
item_type item;
struct list ∗ next ;
}list;
void reverse_list(list **l){
}
Question 4 (50 points)
Implement a stack and solutions to the following problems: balancing parenthesis, evaluating postfix
expressions and transforming infix expressions into postfix expressions.
We are providing some sample code and input files:
public/
balancing.cpp
– main method to check whether an expression is balanced
infix2postfix.cpp
– main method to transform an infix expression into postfix
input_balanced.txt
– test cases for balancing.cpp
input_infix2postfix.txt
– test cases for infixtopostfix.cpp
input_postfixEval.txt
– test cases for postfixEval.cpp
postfixEval.cpp
– main method to evaluate postfix expressions
stack.cpp
– stack implementation
stack.hpp
– stack header file
• To compile, run
$ g++ stack.cpp balancing.cpp
$ g++ stack.cpp postfixEval.cpp
$ g++ stack.cpp infixtopostfix.cpp
• To run each program, run
$ ./a.out
• The test cases follow this format: expected_solution input. Given input, your job is to implement
code that gets the expected_solution. Obviously, you need to calculate expected_solution, not just
print it.
• balancing.cpp must balance round parentheses, and square and curly brackets (() [] {})
• While we provide a few test cases, you are expected to add more to make sure your code works.
Grading:
Implementing the stack is worth 10 points. Solving the balancing problem is worth 10 points, evaluating
postfix expressions is worth 10 points, and transforming infix expressions into postfix is worth another 20
points.
You also have a few opportunities to earn extra credit:
• Transform postfix expressions into infix expressions.
• Evaluate postfix expressions when the operands can be any number (not only one digit). The easiest
way to do this is to use whitespace as a delimiter.
• Transform infix expressions into postfix, but also allow for the sign operator (‘−’). The code we say
in class assumes that all operators are binary, but the sign operator is unary, e.g., −(2∗4).