CSCE 121 Chapter 6

« previous | Wednesday, September 8, 2010 | next »

Building a Program

Analysis: Always think about the big picture and plan logic before writing any code
Design:
Implementation:

Strategy

Know the problem that needs to be solved (know it inside and out)
Break project into logical, manageable parts (even simplify the problem statement
Build a small, limited solution. Keep building small versions until something works.
Build the full-scale solution

A Simple Calculator

Problem Statement: Given expressions as input from the keyboard, evaluate them and write out the resulting value:

2+2 = 4
2+2*3 = 8
2+3-25/5 = 0

First Idea

int main() {
  variables
  while (get a line) {
    analyze the expression
    evaluate expression // what does this mean? How do we do this? (see [[#Writing a Grammar]])
    print result
  }
}

How do we represent 45+5/7 as data?
How do we find 45 + 5 / and 7 in an input string (4 and 5 go together)
How do we make sure that 45+5/7 means 45+(5/7) (order of precedence)

Thinking

Someone has already solved this problem before. Find out what they did, know why it works, and try to implement it yourself.

Writing a Grammar

Grammar Flowchart Illustrating Indirect Recursion

[Expression]: [Term]; [Expression] + [Term]; [Expression] - [Term]

[Term]: [Primary]; [Term] * [Primary]; [Term] / [Primary]; [Term] % [Primary]

[Primary]: [Number]; '(' . [Expression] . ')'

[Number]: Floating-point literal (like -1.2345)

Alternate Notation

E = Expression; T = Term; P = Primary; # = Number

E → T | E '+' T | E '-' T
T → P | T '*' P | T '/' P | T '%' P
P → # | '(' E ')'

Parsing an expression (bottom-up)

'2' → Floating-point literal → Number → Primary → Term → Expression
'+' → Expression
'3' → Floating-point literal → Number → Primary → Term; → Expression

Functions for parsing

get() reads characters and composes tokens; calls cin for input
expression() deals with + and -; calls term() and get(); returns sum/difference
term() deals with *, /, and %; calls primary() and get(); returns product, etc.
primary() deals with numbers and parentheses; calls expression() and get(); returns value

Tokens

in string "1+4*(4.5-6)", 1, +, 4, *, (, 4.5, -, 6, and ) are all tokens: numbers and symbols We need to create a type: get_token() to define tokens (kind and value)

The Program

#include "std_lib_facilities.h"

// Token stuff

double expression(); // declare function so it can be used by primary();
double primary() {
  Token t = get_token();
  switch (t.kind) {
    case '(': {
      double d = expression();
      t = get_token();
      if (t.kind != ')') error("')' expected");
      return d;
    }
    case '#':
      return t.value;
    default:
      error("primary expected");
  }
}
double term() {
  // read and evaluate : 1, 1*2, 1*2/3, etc.
  double left = term();
  while(true) {
    Token t = get_token();
    switch (t.kind) {
      case '*': left *= term(); break;
      case '/': {
        double d = term();
        if (d == 0) error("divide by zero");
        left /= d;
        break;
      }
      default: return left;
}
double expression() {
  // read and evaluate : 1, 1+2, 1+2+3, etc.
  double left = term();
  while(true) {
    Token t = get_token();
    switch (t.kind) {
      case '+': left += term(); break;
      case '-': left -= term(); break;
      default: return left;
}

int main() {
  try {
    while (cin) {
      cout << expression() << endl;
    }
    keep_window_open();
    return 0;
  } catch (runtime_error& e) {
    cerr << e.what() << endl;
    keep_window_open();
    return 1;
  } catch (...) {
    cerr << "exception \n";
    keep_window_open();
    return 2;
  }
}

Recursive Functions: Merge Sort

Take a long list of numbers, divide it in half, and sort each half, etc...

Always have a stopping case: if number of elements in list is small, sort it directly. Otherwise, recurse

Example: Factorial

Recursive definition:

if n = 0, then n! = 1
if n > 1, then n × (n-1)!

int fac(int n) {
  // precondition: n >= 0
  if (n==0) return 1;
  int rest = fac(n-1);
  int result = n*rest;
  return result;
}

int main() {
  fac(4);
}

VERY MEMORY-EXPENSIVE!