Exercise
- As for stacks, another operation
top()
(also known aspeek()
) is often used. It works likepop()
, but it will keep the item in the stack. Please implementpeek()
method in Java or Python.
- In stack.py, we would often expect that
len()
can be used directly like other collections in Python:
s = Stack()
print(len(s))
Please make it possible for Stack
.
Hint: you can refer to Python __len__()
Magic Method.
- In evaluate.py,
if
statement is used to determine the evaluation logic:
if op == '+':
v = vals.pop() + v
elif op == '-':
v = vals.pop() - v
elif op == '*':
v = vals.pop() * v
elif op == '/':
v = vals.pop() / v
Please try to refactor via operator module to simplify the code.
Hint: you can refer to Turn string into operator.
- The current implementation for Dijkstra's two-stack algorithm for expression evaluation (evaluate.py, Evaluate.java) only support
+
,-
,*
, and/
. Please add thesqrt
operator that takes just one argument.
v = evaluate.compute('( ( 1 + sqrt ( 5.0 ) ) / 2.0 )')
print(v)
- Please implement matching parentheses and arithmetic expression evaluation based on ArrayListStack.java using Java respectively.
- The theoretical analysis shows that the time complexity of
dequeue()
of circular queues is \(O(1)\). Please design experiments and visualize your results to validate this theoretical cost based on circular_queue.py.
- The built-in
id()
function returns the memory address, and You can also check if two variables are pointing to the same object usingis
operator. Try to use those two methods to validatea
andb
point to the same object:
a = [1, 2, 3]
b = a
- Please implement a queue based on
ArrayList
in Java.
- As for queues, another operation
first()
(also known aspeek()
) is often used. It works likedequeue()
, but it will keep the item in the queue. Please implementpeek()
method in Java or Python based on circular queues.
- Please implement a deque based on circular arrays in Java.
- Postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if "(exp1)op(exp2)" is a normal fully parenthesized expression whose operation is
op
, the postfix version of this is "exp1 exp2 op".
So, for example, the postfix version of "((5 + 2) * (8 − 3))/4" is "5 2 + 8 3 − * 4 /". Describe an algorithm to evaluate an expression in postfix notation. For simplicity, the numbers and operators are separated with a space.