Lecture Notes: Infix/Reverse Polish Notation, Stacks, and Set ADT (Greek University Course)

A comprehensive set of vocabulary-style flashcards covering infix, postfix, and Reverse Polish Notation (RPN); stack concepts and operations; and Set Abstract Data Type (ADT) concepts and implementations.

Infix notation

A form where operators are written between operands (e.g., A * B); parentheses are often used to specify the intended order of operations.

Unary operator

An operator that acts on a single operand (e.g., negation or plus/minus in front of a number).

Binary operator

An operator that acts on two operands (e.g., +, −, ×, ÷).

Operand

An element on which an operator acts in an expression.

Operator

A symbol that denotes an operation to perform on operands (e.g., +, -, *, /).

Postfix notation

Also known as postfix or Reverse Polish Notation; operators come after their operands (e.g., A B *).

Reverse Polish Notation (RPN)

A postfix expression format used for easy evaluation with a stack; no parentheses are required.

Infix to postfix conversion

A process (often via a stack) to convert an infix expression to a postfix expression, considering operator precedence and associativity.

Example of an RPN expression

An expression like (A × B) − (C + D) can be written in RPN as A B × C D + −.

Stack (LIFO)

A last-in, first-out data structure used to hold operands or operators during RPN evaluation or infix-to-postfix conversion.

Push

Operation that inserts a new element onto the top of a stack.

Pop

Operation that removes and returns the top element from a stack.

Top

The index or pointer indicating the position of the current top element of a stack.

CreateStack

Initialize an empty stack (e.g., set Top to -1 in an array-based implementation).

EmptyStack

A check to determine if a stack has no elements (usually Top == -1).

FullStack

A check to determine if a stack has reached its capacity (based on a predefined limit).

StackADT

An abstract data type interface for stacks, defining operations like CreateStack, Push, Pop, and EmptyStack.

Stack memory representation with array

Stacks can be implemented using an array with a Top index to track the current top element.

Algorithmic use of stack for RPN evaluation

To evaluate an RPN expression, push operands onto the stack and, when an operator is encountered, pop the required number of operands, apply the operator, and push the result back.

Set

A non-ordered collection of distinct elements; membership is expressed as x ∈ A.

Universal set

The set that contains all objects being considered for a problem; e.g., the digits 0–9.

Membership

Relation indicating whether an element belongs to a set (x ∈ A) or does not belong (x ∉ A).

Union of sets

The set of elements that are in A or in B or in both (A ∪ B).

Intersection of sets

The set of elements that are in both A and B (A ∩ B).

Difference of sets

The set of elements that are in the first set but not in the second (A − B).

Empty set

A set with no elements; denoted Ø or {}.

Subset

A set S1 is a subset of S2 if every element of S1 is also an element of S2 (S1 ⊆ S2).

Equality of sets

Two sets are equal if they contain exactly the same elements.

Set ADT implemented with an array (in C)

An array-based representation where a boolean array indicates membership of each element of the universal set; used to implement operations like insert, delete, union, intersection, and difference.

Membership test (in a Set ADT)

Function that checks if a given element is in a set by testing its corresponding boolean flag in the membership array.

Insert into a set

Add an element to a set by marking its membership flag as true.

Delete from a set

Remove an element from a set by marking its membership flag as false.

Union operation in a Set ADT

Create a new set whose membership flags are true wherever either input set has true membership.

Intersection operation in a Set ADT

Create a new set whose membership flags are true only where both input sets have true membership.

Difference operation in a Set ADT

Create a new set with elements that are in the first set but not in the second.

Subsetting test

Check if every element of one set is also an element of another set.

Equality test in Set ADT

Check whether two sets have identical memberships for all elements in the universal set.