Explain why Reverse Polish notation is sometimes used instead of infix notation.
- Removes use of brackets
- Easier for a machine/computer to evaluate
- simpler to code algorithm
- Operators appear in the order required for computation
Explain how a stack could be used in the process of evaluating an expression in Reverse Polish notation.
- (Starting at LHS of expression) push values/operands onto stack
- Each time an operator is reached pop top two values off stack and apply operator to them, (Except when the operator is an exponential or unary minus)
- Add result (of applying operator) to stack
What is the syntax of a language?
The set of rules that define a valid statement.
What is backus-naur form a type of?
It’s a type of meta-language
Why do we use meta-languages instead of just regular expressions?
- Regular expressions are lengthy and time consuming to define
- Meta-languages can do this more succinctly (briefly and clearly expressed)
What does : := mean in backus-naur form?
it means “is defined by”
What is the notation for a statement in backus-naur form?
LHS : := RHS
Give the names of each of the components in the following backus-naur form statement:
: := 0|1|2|3|4|5|6|7|8|9
: := 0|1|2|3|4|5|6|7|8|9
is a meta component / syntactic variable
: := and | are meta symbols
What is each individual rule called in backus-naur form?
They are called a production
Give an example of using recursion in backus-naur form?
: := |
What is parsing and how is it achieved?
- Ascertaining whether a given statement is valid
- Done by replacing meta variables with more comprehensible meta variables at each stage.
What is a syntax diagram?
- A graphical method of representing the syntax of a language
- Maps directly to BNF
What does an oval shape mean in a syntax diagram?
This is a terminal element (so it cannot be broken further broken down)
What does an rectangle shape mean in a syntax diagram?
This is a non-terminal element which will be defined in another syntax diagram
What does an arrow around the rectangle shape mean in a syntax diagram?
This is a non-terminal element that may be used more than once
What is the other name for reverse polish notation?
Postfix notation
What is Reverse polish notation?
It is a method of writing arithmetic expressions
What are the advantages of using Reverse polish notation?
- It eliminates the need for brackets
- It produces expression in a form suitable for evaluation using a stack
What is the normal/human way arithmetic expressions are written?
Arithmetic expressions are usually written in infix notation
What is the order of precedence in Reverse Polish Notation?
= ( \+ - ) */ ^ - (unary minus, as in -3 + 2)
How do we know that an expression is in infix notation?
Because the operator is written in between operands (numbers)
How do we know that an expression is in postfix notation?
Because the operator is written after the operands (numbers)
What are the steps to translate from postfix to infix?
- Scan the expression until you find two operands followed by an operator
- Bracket the next two operands with the operator between them
- Continue writing down operands until you find the next operator, which will operate on the preceding operands
What type of expression will traversing an in-order binary tree give?
It will give an algebraic expression in infix format
-
Data Types32
-
Problem solving14
-
Finite State Machines / The Turing Machine26
-
Searching and sorting algorithms21
-
Maths for Regular Expressions/sets/subsets46
-
Data Structures21
-
Recursive algorithms17
-
Trees/Tree traversals20
-
Dijkstra's shortest path13
-
Backus-Naur Form/Reverse Polish Notation27
-
Regular expressions/regular language10
-
Procedural programming2
-
Big O Notation20
-
Graph-traversal algorithms7
-
Limits of Computation14
-
Queues19
-
Stacks17
-
Hash Tables/Dictionaries27
-
Graphs17
