### Algorithm Questions - Series 2

### Stack/Queue Algorithm Questions

**Balanced--symbol checker**

1. Read the symbol until EOF.

2a. If the symbol is an opening symbol, put it into the stack.

2b. If it is a closing symbol:

i. If the stack is empty, report error.

ii. Otherwise, pop the stack, if it's not the corresponding closing symbol, report an error.

3. At the end, if there is still element in the stack, report an error.

**Postfix notation**

In a postfix expression, an operator always follows its operands. Brackets and parentheses are unnecessary; we can simply traverse it and compute the result.

The algorithm for evaluating any postfix expression:

* While there are input tokens left

o Read the next token from input.

o If the token is a value

+ Push it onto the stack.

o Otherwise, the token is an operator (operator here includes both operators, and functions).

+ It is known a priori that the operator takes n arguments.

+ If there are fewer than n values on the stack

# (Error) The user has not input sufficient values in the expression.

+ Else, Pop the top n values from the stack.

+ Evaluate the operator, with the values as arguments.

+ Push the returned results, if any, back onto the stack.

* If there is only one value in the stack

o That value is the result of the calculation.

* If there are more values in the stack

o (Error) The user input has too many values.

**Infix to postfix conversion**

Read the token of infix expression

If it is operand, immediately output it.

If it is open parenthesis, put it to stack.

If close parenthesis, pop back symbols until an open parenthesis appears.

If operator, pop all symbols until a symbol of lower precedence or a right-associative symbol of equal precedence appears, then push the operator.

At the end, pop all remaining stack symbols.

Q. How to use array or list to implement a stack/queue.

Q. Use a single array to implement three stacks

1. Divide the array in three equal parts and allow the individual stack to grow in that limited space.

Q. Design a stack which, in addition to push and pop, also has a function min which returns the minimum element?

Use an additional stack which keeps track of the mins.

```
public void push(int value){
if (value <= min()) { s2.push(value); }
super.push(value);
}
public Integer pop() {
int value = super.pop();
if (value == min()) { s2.pop(); }
return value;
}
```

Q. Implement a data structure SetOfStacks, which should be composed of several stacks, and should create a new stack once the previous one exceeds capacity.

Implement a function popAt(int index) which performs a pop operation on a specifc sub-stack

class SetOfStacks

{ ArrayList stacks = new ArrayList();}

Push operates on the last stack, if the last stack is at capacity, we need to create a new stack.

Pop also operate on the last stack, If the last stack is empty (after popping), then we should remove it from the list of stacks.

**Q. Implement a queue using two stacks**

S1 will be ordered with the newest elements on the top, while s2 will have the oldest elements on the top.

We push the new elements onto s1, and peek and pop from s2. When s2 is empty, we’ll transfer all the elements from s1 onto s2, in reverse order

Q. sorts a stack in ascending order.

Method signature: Stack sort(Stack s).

```
public static Stack<Integer> sort(Stack<Integer> s) {
Stack<Integer> r = new Stack<Integer>();
while(!s.isEmpty()) {
int tmp = s.pop();
while(!r.isEmpty() && r.peek() > tmp) {
s.push(r.pop());
}
r.push(tmp);
}
return r;
}
```

Resources