- Some problems don't lend themselves to solutions described only in terms of objects. This is one of them.
-
- Approach:
- Step 1: identify those things that are objects in this problem.
- Each object:
- - consists of .. (is/ has)
- - operates on...
- - reports on...
-
- 1. Calculator Language definition - how to read the notation & what it means
- <operand> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
- <operator> ::= + | - | * | /
- (binary operators only; evaluated left to right; normal precedence: i.e. */ before +-)
- <expression> ::= <operand> |
- <expression> <operator> <expression> |
- (<expression>)
- <statement> ::= <expression>;
-
- 2. What is parsing (a simple explanation)
- An algorithm or program to determine the syntactic structure of a sentence or string of symbols in some language. A parser normally takes as input a sequence of tokens output by a lexical analyser. It may produce some kind of abstract syntax tree as output.
-
- 3. How to parse expressions (work through sample expressions)
-
- 4. Outline of solution:
-
- The basic idea is that this program is "event-driven". It is to toggle between 'states', first looking for a number (N) then looking for a symbol (SY). The state determines which symbol you are looking for and will accept. The brackets fit in as described below.
-
- There should be 2 stacks: one for numbers and one for symbols.
- nest = 0;
- state = N; // N, Sy
-
- '(' allowed after + - * /
- after (
- state = N // remains unchanged
-
- ')' allowed after N
- after ')'
- state = Sy // remains unchanged
- Rough Algorithm:
- ReadToken: get char
- if ';' return semi
- if 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ( return operand (N)
- if + - * / ) return symbol (Sy)
- Evaluate: PopSy // must be + - * /
- PopN N1
- PopN N2
- evaluate N2 Sy N1 // exception: Sy = '/' and N1 = 0
- PushN (result)
- ReadToken
- OPERAND:
- if state == N
- if '('
- PushSy ('(')
- nest++
- else
- PushN (N)
- state = Sy
- else
- ERROR: ('Symbol Expected')
- Exit (1)
-
- SYMBOL:
- if state == Sy
- '+' | '-': check top of SyStack
- if + | - | * | /
- Evaluate
- PushSy (Sy)
- State = N
- '*' | '/' : check top of SyStack
- if * | /
- Evaluate
- PushSy (Sy)
- State = N
- ')' : repeat: Evaluate
- check top of SyStack
- if '('
- PopSy
- nest--
- break
- default: ERROR ('Symbol Expected')
- Exit (1)
- else
- ERROR: ('Operand Expected')
- Exit (1)
-
- SEMI:
- if state == N ('Operand Expected')
- if nest != 0 ('Missing Parentheses')
- if Stack not empty ('Premature End of Expression')
-
- end