User Rating:  / 0
PoorBest 

My latest programming adventure has been with an old, yet not forgotton, project: the TemplateEngine Library.

It was an idea that began as i was developing another program, i was writing a program to generate php and in particular phpbb mod code.

I began with the idea of generating in memory the php code for each file that would be required, i quickly saw that it would entail a lot of coding and it would all be hard-coded (to an extent). It occured to me to then use a base template file that had most of the code i wanted already written, and to replace the bits and pieces i wanted with particular variables, the most obvious ones being the name of the package, author, version etc.

For those that havent seen what a php (or phpbb mod) file looks like here is a partial example of the header of a phpbb mod file:

<?php
/**
 *
 * ucp_afkmanager [English]
 *
 * @package AFK Manager
 * @version $Id: 0.3.0
 * @copyright (c) 2009 -[Nwo] fearless
 * @license http://opensource.org/licenses/gpl-license.php GNU Public License
 *
 */
 
/**
 * DO NOT CHANGE
 */
define('IN_PHPBB', true);
 
if (empty($lang) || !is_array($lang))
{
  $lang = array();
}

I had wrote some code to implement a crude but effective way of replacing defined 'variables' with their associated text strings in the file as it was rewritten out to its new location. Because php (and phpbb mods) are case sensitive, i realised that the ability to specify upper, lowercase and/or propercase (title-case) strings would be handy and i incorporated extra variables to do so.

<?php
/**
 *
 * @package %%PROJECTNAME%%
 * @version $Id: %%PROJECTVERSION%%
 * @copyright %%PROJECTCOPYRIGHT%%
 * @license http://opensource.org/licenses/gpl-license.php GNU Public License
 */
 
/** 
 * DO NOT CHANGE 
 */
if (!defined('IN_PHPBB'))
{   
  exit;
}

I made %%PROJECTNAME%%, %%projectname%% and %%ProjectName%% variables to replace strings for. One for upper, lower and proper case. I began thinking it would be nice to wrap all this up in a library for each of re-use (for other projects and potential ideas i had). But the case thing bothered me. If i could add some sort of string functions to the variables - %%UPPER(projectname)%% it would be nicer and easier to use for the end user. Something to ponder on, but for the time being i went ahead and took most of the code i had written and reworked it for my TemplateEngine library.

I had gotten to the point in my library where the variable is replaced and i left the code at that point, to do other projects. I could have easily finished it for replacing variables but the function thing still bothered me. I knew i wanted that in it and for the time being didnt know how to accomplish it. So the TemplateEngine project moved into a dormant phase.

Fast forward to a couple weeks ago when i decided to revive the project. Over the time i had left the project, i had slowly added more ideas and thoughts generated from working on other projects that built up to allow me to see the possiblity of using this knowledge to perhaps apply to the TemplateEngine library. Dynamic structure memory allocation and virtual stacks are a few of the 'ideas' or thought-nuggets that helped complete this last puzzle, how to implement an evaluation of a function.

Most of the work done recently is a direct reference to what is known as converting infix expressions to postfix expressions for evaluation. In the last week or so i read up a lot about tokenizing, parsing, stacks and infix and postfix. Im glad to say i finally figured out how to do all this and began implementing the code i needed. I broke the tasks down into a couple of functions: GetInfixTokens, InfixToPostfixTokens, and PostfixEvaluation. For all this i also needed to create functions for creating and managing a virtual stack for push/pop.

The GetInfixTokens is a function to loop throught the expression string and take out each part and put it into a list in memory. Typically each part is either a operand (a number, a string, a variable) or an operator (a function name, a mathmatical operator: = - / *). I roughly approximated this approach and modified it slightly for my own usage, but in essence it is the same.

The InfixToPostfixTokens function is where it starts to get interesting, with the use of virtual stacks, the function re-orders the infix tokens in a particular order. The basic rule for this (slighly modified for my own use) is:

  • If token is an operand (a number), create a new postfix token in our postfix tokenlist
  • if token is a left bracket, push it onto our virtual stack (opstack)
  • if token is a right bracket, pop the opstack until it is not a left bracket (and ignore the left bracket), and create a postfix token of the popped opstack item, and add it to our postfix tokenlist
  • If token is a string, check to see if string matches one of our functions, if it is then push it onto opstack. If it isnt a function name, we assume its a variable, so we create a postifx token and add it to our postifx tokenlist
  • If where at the end of our infix tokens and the stack still has items on it, pop each item off opstack and create a postfix token and add it to our postix tokenlist (ignore any left brackets popped)

Here is an example, using UPPER(LEFT(varname,3)) as our expression: (The image shows the virtual stack as we process each token)

Functions and left brackets are pushed onto the stack until we reach varname, we create a postfix token and add it to our postfix tokenlist. The next token is '3', which we convert to an integer and create a token for and push it onto our tokenlist. Then we come across the ')' and pop the stack, we get a '(' so we pop until is not a '(' which gives us 'LEFT', create a token for it and push onto tokenlist. Next is ')', and again we pop until we reach 'UPPER', create token for it and push onto tokenlist.

Our final ouput will be: varname 3 LEFT UPPER

Now we can begin the evaluation of this in our PostfixEvaluation function. The basic steps for this are:

  • If token is a variable, get the variable's value (only string type supported at the moment) and push the string onto our virtual stack
  • If token is a number push it onto our stack
  • If token is a function, pop stack a nuumbe rof times(depends on function) and evaluate. For LEFT, we pop the stack twice: 1st pop is our argument, 2nd pop is the string. For UPPER we pop the stack once, 1st pop is the string. The result is returned onto the stack.
  • If no more tokens left to process the stack should hold our final expression value and this is returned.

Here is an example of how it works, using varname 3 LEFT UPPER as our postfix expression: (The image shows the virtual stack as we process each postfix token and evaluate)

First token we reach is our varname, a variable - which we retrieve the value for, a string which is "Tester" and we push it onto the stack. The second token is a number, 3, which we push onto the stack. The third token is LEFT, so we pop the stack twice, once for the numeric argument, 3 which we store to a temp variable, pop again for the string. We call the left function and push the ouput string to our stack: "Tes". The fourth token is UPPER, we pop the stack once, which gives us the string. We call the upper function and push the ouput string to the stack: "TES".

No more tokens left, so we pop the stack the last time to return our expression result: "TES"

So with all that, ive still more work to do, error checking and processing, deciding what to do if an error occurs, and the possiblity of adding more operators like + to concat a string for example, and possibly handling other variable types: numeric, logical etc. For what i want to do with my TemplateEngine i think i may leave it which a functional but restrictive set of functions for working with strings only, but time will tell.

Category: Blog

Login Form