g12-01.cpp

游戏开发数据结构Data Structures for Game Programmers

    // ============================================================================
// G12-01.cpp
// Parsing an arithmetic expression
// ============================================================================
#include "SDLGUI.h"
#include "BinaryTree.h"
#include "Queue.h"
#include <stdlib.h>
#include <string.h>


// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Game Demo 12-01: Parsing Demo";
const int WIDTH             = 800;
const int HEIGHT            = 600;
const int ITEMS             = 32;
const int ARIAL             = 0;


// ============================================================================
//  Classes
// ============================================================================
enum TOKEN
{
    VOID,           // invalid token
    NUMBER,         // any float or int
    VARIABLE,       // c, s, t, or l
    OPERATOR,       // +, -, *, /
    LPAREN,         // (
    RPAREN          // )
};


class Token
{
public:
    TOKEN m_type;       // what type of token is it?
    float m_number;     // if number, what number is it?
    int m_variable;     // if a variable, which variable? 
    int m_operator;     // if an operator, which operator?
};



// ============================================================================
//  Global Variables
// ============================================================================
SDLGUI* g_gui;

// the queue of tokens before they are parsed.
LQueue<Token> g_queue;

// the strings for the x and y locations
char g_xstring[64] = "";
char g_ystring[64] = "";

// the current time of the simulation
char g_time[64] = "";

// the life of the player
char g_life[64] = "100";

// the player bitmap
SDL_Surface* g_playerbmp = 0;

// the players position
int g_x = 0;
int g_y = 0;

// is the simulation running?
bool g_running = 0;

// should it show the tree?
bool g_showtree = false;

// the last time the timer was recorded
int g_timer;

// the current time of the simulation
int g_currenttime;

// the parse trees
BinaryTree<Token>* g_xtree = 0;
BinaryTree<Token>* g_ytree = 0;

// the array of variables (cosine, sine, time, life)
float g_vars[4];

// the four operators
char g_operators[4] = { '+', '-', '*', '/' };

// the four variable names
char g_variables[4] = { 'c', 's', 't' ,'l' };


// ============================================================================
//  Draw Algorithms
// ============================================================================
void DrawNode( BinaryTree<Token>* p_node, int p_x, int p_y )
{
    static SDL_Surface* text;
    static char number[32] = "";

    // draw the contents of the circle.
    switch( p_node->m_data.m_type )
    {
    case VARIABLE:
        // draw the variable name
        number[0] = g_variables[p_node->m_data.m_variable];
        number[1] = 0;
        break;
    case OPERATOR:
        // draw the operator symbol
        number[0] = g_operators[p_node->m_data.m_operator];
        number[1] = 0;
        break;
    case NUMBER:
        // draw the actual number
        sprintf( number, "%f", p_node->m_data.m_number );
        break;
    }

    text = TTF_RenderText_Shaded( g_gui->GetFont(ARIAL), number, BLACK, WHITE );

    g_gui->Blit( text, (48 - text->w) / 2 + p_x, 
                       (48 - text->h) / 2 + p_y );
    SDL_FreeSurface( text );

}


void DrawTree( BinaryTree<Token>* p_tree, int p_x, int p_y, int p_width )
{
    if( p_tree != 0 )
    {
        // draw the current node
        DrawNode( p_tree, p_x + (p_width / 2) - 24, p_y);

        int w = p_width / 2;
        int w2 = w / 2;

        // recursively draw the left and right child trees
        if( p_tree->m_left )
        {
            DrawTree( p_tree->m_left, p_x, p_y + 128, w );
            g_gui->ArrowLine( p_x + (p_width / 2), p_y + 24, 
                              p_x + w2, p_y + 152, 24, 24, false, true, BLACK );
        }
        if( p_tree->m_right )
        {
            DrawTree( p_tree->m_right, p_x + w, p_y + 128, w );
            g_gui->ArrowLine( p_x + (p_width / 2), p_y + 24, 
                              p_x + w2 + w, p_y + 152, 24, 24, false, true, BLACK );
        }
    }
}


// ============================================================================
//  Functions
// ============================================================================

// this reads a float from a string and returns the actual float value.
// p_index should point to the starting point, and will represent
// the end of the float when the reading is complete.
float ReadFloat( char* p_string, int& p_index )
{
    float f = 0.0f;
    char c = p_string[p_index];
    float divisor = 10.0f;

    // read the front part of the float in first
    while( c >= '0' && c <= '9' )
    {
        // multiply the current float by 10, then
        // add the current character to the current float
        // (ie: if f was 1.0 and c is '4', then after these
        // steps, f will be 10.0, then 14.0)
        f *= 10.0f;
        f += (float)(c - '0');

        // read the next character
        p_index++;
        c = p_string[p_index];
    }

    // load the back part of the float, if there is a period
    if( c == '.' )
    {
        // skip past the period and read the next char
        p_index++;
        c = p_string[p_index];

        // while there are numbers, read them in
        while( c >= '0' && c <= '9' )
        {
            // add "c/divisor" to the float.
            // when this starts out, divisor is 10,
            // so if the first number after the period is 3, 
            // then this adds 3/10 to the float. Then
            // it multiplies the divisor by 10, so if the next
            // number is 7, it adds 7/100, and so on.
            f += (float)(c - '0') / divisor;

            // multiply the divisor by 10.
            divisor *= 10.0f;

            // read the next char
            p_index++;
            c = p_string[p_index];

        }
    }
    return f;
}


// scan the string, and convert it into a queue of tokens
void Scan( char* p_string, LQueue<Token>& p_queue )
{
    int index = 0;
    int length = strlen( p_string );
    char c;

    Token t;


    while( index < length )
    {
        // read the character in, and assume it is invalid to begin with.
        c = p_string[index];
        t.m_type = VOID;

        // find out what kind of token it is.
        switch( c )
        {

        // parenthesis
        case '(':
            t.m_type = LPAREN;
            break;
        case ')':
            t.m_type = RPAREN;
            break;

        // operators
        case '+':
            t.m_type = OPERATOR;
            t.m_operator = 0;
            break;
        case '-':
            t.m_type = OPERATOR;
            t.m_operator = 1;
            break;
        case '*':
            t.m_type = OPERATOR;
            t.m_operator = 2;
            break;
        case '/':
            t.m_type = OPERATOR;
            t.m_operator = 3;
            break;

        // variables
        case 'c':
            t.m_type = VARIABLE;
            t.m_variable = 0;
            break;
        case 's':
            t.m_type = VARIABLE;
            t.m_variable = 1;
            break;
        case 't':
            t.m_type = VARIABLE;
            t.m_variable = 2;
            break;
        case 'l':
            t.m_type = VARIABLE;
            t.m_variable = 3;
            break;

        // numbers
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            t.m_type = NUMBER;
            t.m_number = ReadFloat( p_string, index );
            index--;
            break;
        }

        // if the token was valid, enqueue it.
        if( t.m_type != VOID )
            p_queue.Enqueue( t );

        index++;
    }
}


// parse a queue of tokens into a binary tree node
BinaryTree<Token>* ParseArithmetic( LQueue<Token>& p_queue )
{
    BinaryTree<Token>* left = 0;
    BinaryTree<Token>* center = 0;
    BinaryTree<Token>* right = 0;

    // make sure the queue has something in it.
    if( p_queue.Count() == 0 )
        return 0;

    // take off the first token, and determine what it is
    switch( p_queue.Front().m_type )
    {

    // if the first token is a left parenthesis, then pop off the token,
    // and recursively parse what is inside the token.
    // finally, assume that there is a right parenthesis at the front of
    // the queue once complete, and pop that off.