About 4D Systems PTY LTD
4D Systems, Australia
Home Company Products 4DGL Developers Center Support forum Distributors News & Events Contact us App Notes
4DGL - Sharing our bytes to the world

Infix2PostfixDemo1.4DG


Codebase / PICASO-GFX / PICASO-GFX2 and 4DGL Display Modules / Generic Examples / Text and Strings

A rudimentary but complete infix to postfix parser.
No output generator yet, that will be described
In another example.
This demonstrates a lot of string functions, how to
make a simple edit buffer, and many useful techniques.
About this code
Author: The 4D team
Uploaded on: 20/03/2011

Back to previous page

Source code:

#platform "uVGA-II_GFX2"


////////////////////////////////////////////////////////////////////////////////////
// 4DGL Demo Application for Picaso
// A rudimentary but complete infix to postfix parser.
// No output generator yet, that will be described
// In another example.
// This demonstrates a lot of string functions, how to
// make a simple edit buffer, and many useful techniques.
//
// works with all Picaso platforms
//
// save program to FLASH, then use the terminal to communicate.
//
// see http://en.wikipedia.org/wiki/Reverse_Polish_notation for more info
//
////////////////////////////////////////////////////////////////////////////////////

#inherit "4DGL_16bitColours.fnc"



#CONST
    SPACE       0x20
    UNDERLINE   0x5F
    CR          13
    TAB         9
    LF          10
    BS          8
#END

#constant BUFSIZE 20    // text entry buffer size, 4 chars
#constant TEXT_FIELD 32 // text entry print field width

var Textbuf[BUFSIZE];   // text entry buffer
var bufptr;


var outbuf[40];         // postfix output buffer

var number;

var label[9];           // labels up to 16 char allowed


//==============================================================
//==============================================================
//==============================================================
//==============================================================
func main()
    var ch;

    txt_FontID(FONT1);
    gfx_Set(BEVEL_WIDTH,3);

    gfx_Panel(PANEL_SUNKEN,0,260,235,20,GRAY+3);

    updateTextBuf(CR);

    // now just stay in a loop
    repeat
        ch := serin();
        if (ch != -1)
            updateTextBuf(ch);           // if a key was received from PC, process it
        endif

   forever

endfunc
//==============================================================
//==============================================================
//==============================================================
//==============================================================

//==============================================================
// skip tabs or spaces, return 0 if none skipped
//==============================================================
func skipwhites()
    var retval;
    while( iswhite (str_GetByte(bufptr)))             // skip tabs and spaces
        bufptr++;
        retval++;
    wend
    return retval;
endfunc

//==============================================================
// return true if valid number, or zero if not valid number
// number gets the number
// handles H'nnnn' style, and 0x, 0b, and standard decimal only.
//==============================================================
func getNumber()
    var retval := 1;
    // TBD other Mchip number formats
    if(str_Match(&bufptr, "H'"))                    // if its Mchip hex format
        if( !str_GetHexW(&bufptr, &number) ||       // must get valid hex number
            (str_GetByte(bufptr++) != '\''))        // and closing tick
             retval := 0;                           // else bad hex number format
        endif
    else
        if(!str_GetW(&bufptr, &number)) retval := 0;  // get a standard bin,hex or decimal number
    endif
    return retval;
endfunc

//==============================================================
// get a label, advancing bufptr past label
// returns length of label, or zero if invalid label
//==============================================================
func getLabel()
    var c, dest, *src , len;
    dest := str_Ptr(label);                         // point to label buf
    src := bufptr;
    repeat
        c := str_GetByte(bufptr);                   // get the label
        if((c != '_') && !isalnum(c)) break;
        str_PutByte(dest++, c);
        bufptr++;
        len++;
    forever
    str_PutByte(dest, 0);                           // terminate the string
    return len;
endfunc

//==============================================================
// error generator
//==============================================================
func ErrorMessage(var errnum)
    var private errors[10];
    var private e;
    if(!e) // if not yet loaded, set the messages
        errors[e++] := "Unknown error";
        errors[e++] := "Operator expected";
        errors[e++] := "Operand expected";
        errors[e++] := "Unmatched closing parenthesis";
        errors[e++] := "Double Unary";
        errors[e++] := "Unexpected character encountered";
        errors[e++] := "Closing parenthesis expected";
        errors[e++] := "Bad operand";
    endif
    if(errnum >= e) errnum := 0;
    return errors[errnum];
endfunc


// NB must have $ to copy verbatim
#constant legalchars $"=|^&+-*/%<>!"

#DATA
    byte precedence 0,1,2,2,3,4,4,5,5,5,5,5,6     // precedence table must match legalchars
#END

//======================================================================
// This table lists the operators in order of decreasing precedence.
// When several operators are listed in the same row, this indicates
// that they share the same levelof precedence.
//  Operator            Description
//  !                   6 Unary not and assign
//  *  /  %  <<  >>     5 Binary multiplying operators
//  +  -                4 Binary adding operators
//  &                   3 Bitwise boolean and
//  | ^                 2 Bitwise boolean or and xor
//  =                   1 Assignment
//======================================================================
// get precedence of operator
func GetPrec(var c)
    return precedence[ lookup8(c, legalchars) ];
endfunc

//======================================================================


// enumeration for the state machine
#constant NONE, FUNCTION, OPERAND, OPERATOR, UNARYOP

//======================================================================
// convert infix to reverse polish (postfix)
// returns 0 if ok, else error number
// note the < and > are used to denote << and >>
// As there are no relational operations, this
// will not pose a problem, however, in a real
// working application, the postfix output string
// would be tokenized.
//======================================================================
func InfixToPostFix(var ibuf, var obuf)

    var n, state, balance, sp, ch, errnum;

    var stack[20];

    bufptr := str_Ptr(ibuf);                                  // raise a string pointer to the input buffer

    to(obuf); putch(' ');                                     // send first char to buffer so APPEND will work

    skipwhites();                                             // skip any lead whitespace

    while((ch := str_GetByte(bufptr)) && !errnum)             // while we have input, and no errors have occured,

        // ? number
        if(getNumber())                                       // if its a number
            if (state != OPERAND)                             // and last item wasn't an operand
                //to(APPEND); print([HEX4] number," ");       // copy number to outbuf, always as hex4
                to(APPEND); print(number," ");                // copy number to outbuf
                state := OPERAND;                             // item is now operand
            else
                errnum := 1;                                  // err, "Operator expected";
            endif

        // ? '('
        else if (ch == '(')
            bufptr++;
            if (state == OPERAND)
                errnum := 1;                                  // "Operator expected";
            else
                if(state == UNARYOP)
                    state := OPERATOR;                        // allow additional unaries
                endif
                stack[sp++] := ch;                            // save token
                balance++;                                    // parenthesis balance
            endif

        // ? ')'
        else if (ch == ')')
            bufptr++;
            if (state != OPERAND)                             // ')' must follow operand
                errnum := 2;                                  // "Operand expected";
            else
                if (balance <= 0)
                    errnum := 3;                              // "Closing parenthesis without opening parenthesis";
                endif
            endif

            while ((ch := stack[--sp]) !=  '(')               // pop til we find balance
                to(APPEND); print([CHR] ch," ");
            wend
            balance--;                                        // parenthesis balance

         // ?  '=', '|', '^', '&', '+', '-', '*', '/', '%', '<', '>', '!'
         else if(lookup8(ch, legalchars))
            bufptr++;

            if(ch == '<' || ch == '>')                        // check for << and >>
                if(str_GetByte(bufptr) != ch)
                     errnum := 7;                             // "Bad operand";
                else
                    bufptr++;
                endif
            endif

            if (state == OPERAND)                             // pop operators with higher or same
                while (sp)
                    if (GetPrec(stack[sp-1]) < GetPrec(ch)) break;
                    to(APPEND); print([CHR] stack[--sp]," ");
                wend
                stack[sp++] := ch;                            // push the operator
                state := OPERATOR;

            else if (state == UNARYOP)                        // can't have 2 unaries
                errnum := 4;                                  // "Double Unary";

            else if (ch == '-' )                              // handle unary ops
                state := UNARYOP;
                stack[sp++] := '!' ;                          // save unary NOT token

            else if (ch == "+")                               // ignore unary +'s
                state := UNARYOP;
            else
                errnum := 2;                                  // "Operand expected";
            endif

        // ? exit
        else if(ch == ';' || ch == ',')
            break;                                            // break on break delimeter


        // label ?
        else if (n := getLabel())                             // finally, can only be a label or function


            if (state == OPERAND)                             // if cureently an operand
                errnum := 1;                                  // "Operator expected";
            else
                to(APPEND); print([STR] label," ");
                state := OPERAND;
            endif

        else
            // **** expand here as required
            errnum := 5;                                      // else error, "Unexpected character encountered";
        endif

        skipwhites();       // skip tabs and spaces

    wend // loop til parsed

    // final error checking
    if (state == OPERATOR || state == UNARYOP)                // if operator was expected
        errnum := 2;                                          // error "Operand expected";
    else if (balance)                                         // if balance not zero
        errnum := 6;                                          // "Closing parenthesis expected";
    endif

    if(!errnum)                                               // if no errors
        while (sp)                                            // unstack any remaining items
            to(APPEND); print([CHR] stack[--sp], " ");
        wend
    endif

    return errnum;      // return 0, or error code

endfunc


// process the text buffer
func process()
    var n, err;

    err := InfixToPostFix(Textbuf, outbuf);                   // do the conversion

    gfx_MoveTo(0,10); putstr("INPUT:\n");
    
    n := 0;
    while(n++ < TEXT_FIELD) putch(' ');                        // blank screen area
    txt_FGcolour(CYAN);
    print("\r ", [STR] Textbuf);

    gfx_MoveTo(0,50); putstr("OUTPUT:\n");

    n := 0;
    while(n++ < TEXT_FIELD) putch(' ');                        // blank screen area
    txt_FGcolour(LIME);

    if(err)
        print("\r", [STR] ErrorMessage(err));                  //  print error
    else
        print("\r", [STR] outbuf);                            //  or result
    endif


endfunc


//======================================================================
// update the text window, process text if CR received
// TBD expand so line can be longer than window.
//======================================================================
func updateTextBuf(var ch)
    var private *p, cursor, full;

    if (ch == CR)                                             // if carriaghe return

       str_PutByte(p, 0);                                     // terminate the buffer

       process();                                             // process the text

        p := str_Ptr(Textbuf);                                // reset the pointer

        mem_Set(Textbuf, SPACE, TEXT_FIELD);                  // clear the buffer to all spaces
        str_PutByte(p+TEXT_FIELD, 0);                         // terminate it
        str_PutByte(p, UNDERLINE);                            // place the cursor

         cursor := 0;                                         // reset cursor
    else
        if (ch == BS)
            str_PutByte(p, SPACE);                            // blank current pos
             if(!full)                                        // if buffer not full
                if (cursor)
                    cursor--;
                    p--;                                      // backup
                endif
            endif
            str_PutByte(p, UNDERLINE);                        // place the cursor
            full := 0;                                        // reset flag
        else
            str_PutByte(p, ch);
            if (cursor < TEXT_FIELD-1)
                cursor++;
                p++;
                str_PutByte(p, UNDERLINE);
                full := 0;
            else
                full := 1;
            endif
        endif
    endif
    // now print buffer contents
    txt_Set(TEXT_OPACITY, OPAQUE);
    txt_Set(TEXT_COLOUR, YELLOW);
    gfx_MoveTo(6,266);
    print ( [STR] Textbuf );
endfunc

//======================================================================
//======================================================================
//======================================================================




Copyright © 2007 4D Systems Pty Ltd, Sydney, Australia - All Rights Reserved | Terms and Conditions