Stack applications (expression evaluation, backtracking) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack in data structures?

A stack is a collection that follows the Last In, First Out (LIFO) principle, where the last element added is the first one to be removed.

intermediate

How does a stack help in expression evaluation?

Stacks help evaluate expressions by temporarily storing operators and operands, especially in converting infix expressions to postfix and then calculating the result.

beginner

What is backtracking in computer science?

Backtracking is a method of solving problems by trying possible options and undoing choices when they lead to dead ends, often using a stack to remember previous states.

intermediate

Why is a stack useful in backtracking algorithms?

A stack stores the sequence of choices or states, allowing the algorithm to return to previous points and try different options when a path fails.

intermediate

Explain how postfix expression evaluation uses a stack.

In postfix evaluation, operands are pushed onto the stack. When an operator appears, the required number of operands are popped, the operation is performed, and the result is pushed back. This continues until the expression is fully evaluated.

Which principle does a stack follow?

A Priority Based

B First In, First Out

C Last In, First Out

D Random Access

A stack follows the Last In, First Out (LIFO) principle.

In expression evaluation, what is the main use of a stack?

A To temporarily hold operators and operands

B To store variables permanently

C To sort numbers

D To store the final result only

Stacks temporarily hold operators and operands during expression evaluation.

What does backtracking do when it hits a dead end?

A Stops immediately

B Returns to a previous state to try another option

C Skips to the end

D Deletes all data

Backtracking returns to a previous state to try different options when a path fails.

Which expression type is easiest to evaluate using a stack?

A Postfix

B Prefix

C Infix

D Algebraic

Postfix expressions are straightforward to evaluate using a stack.

In backtracking, what data structure is commonly used to remember previous choices?

A Queue

B Array

C Linked List

D Stack

Stacks are used to remember previous choices in backtracking.

Describe how a stack is used to evaluate a postfix expression.

Think about how you handle numbers and operators step-by-step.

Explain why stacks are important in backtracking algorithms.

Consider how you might remember where you came from when exploring paths.