Week 12: Tutorial Notes

Parsing Arithmetic Expressions

Write a program that reads an arithmetic expression from standard input and constructs an expression tree. Expressions are defined by this grammar, and may also include embedded whitespace.

digit = '0' | '1' | … | '9'

op = '+' | '-' | '*'

const = digit

expr = const | '(' expr op expr ')'

solution

Wythoff's Game

A certain game is played as follows. A chess queen is placed on a 8 x 8 chessboard. Two players alternate moves. On each player's turn, they must move the queen in one of three directions: either rightward, downward, or diagonally down and to the right. The first player to move the queen into the lower-right corner wins.

With perfect play, will the first player win or lose? Write a Windows Forms program that displays an 8 x 8 chessboard. Each square should be colored red if the player whose turn it is to move can always win from that square, blue otherwise.

solution