Nathandelane, Father, Programmer, High Priest

Code Complete

Several months ago I finished reading Steve McConnell's Code Complete 2nd Edition. I learned a lot from it and took notes. Some of what the book contained were methodologies that I already knew and used on a daily basis. Other parts of the book opened my eyes to a higher road in programming. My goal in reading the book was to become a better programmer, a better program designer or architect, and to better understand the reasons behind doing things a certain way. Especially helpful was the fact that most of the practices described in the book were practices we had implemented internally at my current job at the time. So aside from learning new things, they were new things that I was expected to know.

As I said, I already bought into a lot of the material of "Code Complete" before I had read it, but there were some things that I did just because, yet I knew there must be a good reason why I did them. In this next series of posts I am going to review parts of the book by reviewing my notes. I recommend that every programmer read this book. It really applies to everyone at every level, and every programming language. Nobody is exempt. In the past I have talked to some programmers of certain languages and they tried to convince me that "Code Complete" was only for C, C++ and C#. Those are the primary languages referenced in the book, but "Code Complete" is deeper than programming language choice. As I review my notes I may draw information from other sources as well. Please bear with me as I strive to convey my new knowledge in a meaningful fashion.

Valid Reasons to Create a Routine

For all intents and purposes the term "routine" here means any language construct the resembles (per the language) a function, procedure, sub-routine, method, and in some cases accessors and mutators (getters and setters).

1. In order to reduce complexity

   The first reason that Code Complete gives that a programmer may choose to introduce a new routine is to reduce complexity. One of the general examples given was a situation when you might have a nasty long elaborate conditional expression that you want to pop into an if statement. Here is an example:

   namespace Nathandelane.Examples.Conditionals
   {
    public class ShowDifficultConditional
    {
     public ShowDifficultConditional()
     {
      string name = "Nathan Lane";
      string position = "Software Developer";
      int age = 29;
      
      if (name.StartsWith("Na") &&
       name.Contains("La") &&
       (position.Contains("Dev") ||
        position.Contains("Quality"))
       && (age < 35))
      {
       Console.WriteLine("{0} is a young {1} at age {2}", name, position, age);
      }
      else
      {
       Console.WriteLine("{0} is not such a young {1} at age {2}", name, position, age);
      }
     }
    }
   }
   

   I define a "elaborate...conditional expression" as any conditional expression that combines more than a single conditional operator. In this case I have five conditional statements of which two are their own compound conditional. (Aside: I don't normally like to stack my conditional statements, but because this blog has a relatively small amount of horizontal real estate, I chose to display them this way, which in my opinion is pretty ugly. But ignore it for now.)

   The principle of creating a routine to reduce complexity extracts a nasty long elaborate conditional expression into its own routine and replaces its original nastiness with a call to that routine. So in the case of the above, following this principle might look something like this:

   namespace Nathandelane.Examples.Conditionals
   {
    public class ShowDifficultConditional
    {
     public ShowDifficultConditional()
     {
      string name = "Nathan Lane";
      string position = "Software Developer";
      int age = 29;
      
      if (NastyConditionalIsTrue())
      {
       Console.WriteLine("{0} is a young {1} at age {2}", name, position, age);
      }
      else
      {
       Console.WriteLine("{0} is not such a young {1} at age {2}", name, position, age);
      }
     }
   
     private bool NastyConditionalIsTrue()
     {
      bool result = false;
   
      result = name.StartsWith("Na");
      result = result && name.Contains("La");
   
      bool subResult = (position.Contains("Dev") || position.Contains("Quality"));
   
      result = result && subResult;
      result = result && (age < 35);
   
      return result;
     }
    }
   }
   

   Now as you can see the nastiness isn't really gone, but the code complexity has been reduced drastically, and now I can deal with problems in that conditional expression without worrying about making sure that the if statement is formatted correctly, because I can see that it is without thinking too much about it.

   While this principle is cool I wouldn't recommend using it too often. If you have an ugly conditional expression, you may want to re-evaluate your program in general. For example a while back I wrote a parser for a calculator program that had a huge dispatch conditional block that consisted of about thirty nasty embedded conditional blocks. I reworked it several times and it just turned out to always be a mess, and there were always more "if's" and "else if's" to add in. So I changed the whole thing over to the state pattern, did away with all of the conditional-guess-work, and simplified work work greatly. In a way I did follow this principle, but to a greater degree than simply creating a new routine; I created a new class of routines.

2. In order to introduce an intermediate, understandable abstraction

   In my HGrep program I have a lot of elaborate configuration settings. The software itself has 19 documented command-line argument options, some of which have multiple sub-options. The optional command-line arguments that are available is just one method of abstracting the interface for the program into intermediate, more understandable abstractions.

   To better accommodate these abstractions in the code, I create separate methods that provide settings to the agent for each of the possible command-line argument states. The immediate benefit of this is that if one of my arguments changes for some reason, then I can accommodate that change simply in the code by making a change to the method that corresponds to the argument.

3. In order to avoid duplicate code

   This one should be a given to anybody who has been programming for more than a year, even if you're just a hobbyist. Duplicating code is generally speaking a great big no-no. Not that it's really that bad, except when it comes to maintenance. Think about it. What if you had duplicated six line of code 12 times in your program, and one day you decided that two of those lines needed to change. You would really need to make the change to 24 lines, and what would happen if you missed or forgot one? Ideally you would extract those six lines of code into a single routine, and then call that routine in those 12 places in your program. Then when your two-line code change came along, you would only need to worry about changing those two lines of code.

   See how simple that it? It even promotes increased productivity and reduces the likelihood of you making a mistake while making such a change and therefor introducing new defects.

4. In order to support sub-classing

   This principle is an indicator of another of the great design patterns. Allowing for a hook routine is that pattern. Hook routines are routines that may be called by a process, but perhaps doesn't do anything unless it is implemented by the sub class. Basically the unimplemented routine is the hook, and an inheriting class can override that routine to allow for special usage. Hooks

   Hooks allow for dynamically class-enhancing child classes to have a little bit more say in what goes on behind the scenes. One example that I can remember from "Head First Design Patterns" is a pizza store program. This program allowed for the pizza store to implement its own toppings for its pizzas but maintain the same process of making the perfect pizza. The pizza store base class took care of that process, but each implementing pizza store had the ability to add certain toppings, like a special sauce or cheese by overriding certain addTopping() routines.

5. In order to hide sequences

   Probably the most common sequence you might find in programming (especially object-oriented programming), that is also important is the initialization of an object. In object-oriented programming, objects are initialized by a class constructor, which is a special routine found in the class. The constructor is where we usually initialize instance variables, and we can call other private methods to do special tasks if one of the constructor arguments is a state variable.

   Wanting to hide a sequence from the developer using your API is an honorable desire in creating routines. Above I talked about hooks, which are routines that are found in sequences but are left to the implementor to take care of. These hooks, when implemented, may cause minor or significant changes to a sequence. But the sequence is hidden in another routine that ensures the implementor doesn't mess with the overall sequence.

6. In order to hide pointer operations

   In low-level programming languages or programming languages that provide access to the lower levels of operating systems such as C and C++ pointer operations are exposable at the rawest level. Pointer operations can often be confusing, and as such should be encapsulated so that they are more easily maintainable. Some such pointer operations might include allocating and de-allocating memory, instantiation of a class or struct,or even the de-referencing of a pointer. These can all be simplified by wrapping their operations in a high-level routine.

7. In order to improve portability

   Most programming languages are portable across comuter architectures to some extent, but almost all programming languages have some caveats. Some examples might include the inclusion of Win32 API extensions in order to better support Windows 32-bit architectures, or the Curses library to support Intel's console extensibility. One more common instance that we might see for using a method to improve portability comes from JavaScript. JavaScript, though an ECMA standard, still roughly comes in at least two different flavors: Internet Explorer and everything else (stadards-compliance). Because of this many things still differ to some extent across these two general platforms of browsers. Let's take for example th method of attaching events to an object.

   /**
    * alertMe is a function that calls alert with the object passed to it.
    * @param {event} e
    */
   function alertMe(e) {
    alert(e);
   }
   
   someElement = document.getElementById("someElementsId");
   
   if(someElement.attachEvent) {
    // Internet Explorer's method of attaching events:
    someElement.attacheEvent('onclick', alertMe);
   } else {
    // W3C's standard:
    someElement.addEventListener('click', alertMe, false);
    // The third argument above specifies whether the event should bubble up. No control on the event attachment in IE for this.
   }
   

   Now I am certain that I would not want to type that code every time I wanted to attach an event to a particular element, so I might do something like this:

   /**
    * myAttachEvent attaches an event handler to an element based on the
    * browser compatibility.
    * @param {element} element
    * @param {string} eventName Like 'click' or 'mouseover'
    * @param {function} callback
    * @param {bool} bubbleUp (Optional) Whether or not the event should bubble
    * up in the browser (not supported in IE)
    */
   function myAttachEvent(element, eventName, callback, bubbleUp) {
    if(!bubbleUp) {
     bubbleUp = false;
    }
    
    if(element.attachEvent) {
     element.attachEvent('on' + eventName, callback);
    } else {
     element.addEventListener(eventName, callback, bubbleUp);
    }
   }
   

   So now I have a function that will consistently attach events to elements across all [modern] browsers, and it even handles bubbleUp as an optional argument. Most of the time we don't want events to bubble up, so if the argument is null, I set it to false. Once again this is a very good reason for creating a routine, and I use it regularly.

8. In order to simplify boolean tests

   Several times in my experience in programming I have had to deal with the inevitable large list of boolean tests for a single result.Sometimes when you experience this, it means you have a design flaw. However design flaw or not, you have to deal with them. Most languages also offer boolean short circuiting, which makes large boolean tests simpler, but large tests can still become overwhelming. Short ciruiting in boolean tests means that tests are read from left to right and perenthesised conditionals are read in order of outer-most perentheses, so no race conditions apply. Because of short circuiting, the results of a test like this are easy to determine:

   if(true && !false)
   {
    Console.WriteLine("True");
   }
   else
   {
    Console.WriteLine("False");
   }
   

   This expression gets true read first, but if true fails, then !false is never evaluated. In C and C++ short circuiting isn't guaranteed to work, so if you want to ensure that the above appears to get read in order then you have to write:

   if((true) && !false)
   {
    printf("True");
   }
   else
   {
    printf("False");
   }
   

   Anyway back to complex boolean expressions, lets say that you had a number of criteria pertaining to an employee used to determine the number of paid days off they receive during a single year: years with company, number of hours worked per week, employment status (full-time, part-time, contractor, intern), and whether or not they are enrolled in the incentive program. Now let's pretend like you put all of that into a huge conditional (this is obviously bad programming but I'm trying to make a point with what little I have to go on):

   int paidDaysOff = 0;
   
   if(_yearsEmployed > 5 && _weeklyHours >= 30 && (_employmentStatus ==
    Employment.FULL_TIME || _employmentStatus == Emploment.PART_TIME)
    && _incentive == true)
   {
    paidDaysOff = 10;
   }
   ...
   

   While this long conditional is not extremely complex, just the fact that it is long though makes it a good candidate to ensure ease of maintenance and readability:

   bool emplyeeDeserves10DaysOff()
   {
    bool result = _yearsEmployed > 5 && _weeklyHours >= 30 && 
    (_employmentStatus == Employment.FULL_TIME || 
    _employmentStatus == Emploment.PART_TIME) && _incentive
    == true;
    
    return result;
   }
   
   int getPaidDaysOff()
   {
    int paidDaysOff = 0;
    
    if(emplyeeDeserves10DaysOff())
    {
     paidDaysOff = 10;
    }
   }
   

   See how much more readable that is?

9. In order to improve performance

   The final good reason on this list to create a routine is to improve performance.I have had little to no experience with this particular scenario, as either I have not ever had a need to improve performance, or I haven't known a need to improve performance. Either way I hope that if you do find yourself in this situation, that rather than assuming that you need to make a routine, you step back and take a look at the big picture. Are you utilizing your compiler's option to optimize for performance? Are you doing this the way that the programming language publisher recommends you do them? Are you following design patterns or do you just have a mess of code? Also do you have a good set of fully functioning and passing unit tests. These things will help your program to be more efficient, thus increasing performance.

I have many more note pages like this one, and I hope that I have the opportunity to review and share those as well. I hope this was as informative for you as it has been for me. Thanks for letting me take some of your time.

For six years now I have served my time as an IT professional in the Quality Assurance sector. Over that period of time I have tested a wide variety of systems from desktop applications to video games, and from web sites to embedded wifi networked systems. All of these systems required a different means to test them effectively. In each system the same mindset (detail-oriented) was employed, but different techniques were applied to utilize that mindset. In some cases a different toolset was required as well.

For the past three years I have developed and tested web-based solutions and I have come to enjoy the vast amount of software technology available to Quality Assurance professionals today. As I continue my career as a software developer I lean a lot on my past as a QA professional. The following is a list of tools that I have found to be extremely useful in my career.

Web-based Testing

Web-based testing tools are my most recent experience and so I will begin here. This first set of tools are simply browsers that I have found to increase my ability to ensure performance and compatibility metrics.

Browsers

Browsers are the primary tool of the Internet. Customers use browsers of all varieties including those that are no longer supported by the companies who created them. This part is sad, and hopefully we all have the guts to tell our customers that. Last year a man called me up to get support on his Netscape Navigator 9, and I had to tell him that not only do we not support that browser, but neither does the creator. I advised him to move to Firefox, which is similar, because that's what Netscape became, but it is highly supported. Anyway, here's the list of browsers and browser tools I use in my testing efforts:

• IETester from DebugBar is a requirement in my book. IETester gives you the Internet Explorer suite of browsers. It even includes the last currently unsupported Microsoft browser, IE 5.5. But with the lastest installment you get IE 6, IE 7, and IE 8 also. IETester is actively developed, and works very well. It doesn't use emulation, rather it actually collects the old Trident-based rendering engines and allows you to see your web site in different tabs for each browser version.
• Next on my list is Mozilla Firefox. This browser combines tabbed browsing, with ease-of-use, incredible stability, and a huge assortment of supported browser extensions. Some of my required extensions include Firebug, Firecookie, HttpFox, Screengrab, and Modify Headers. Having the ability to be extended with add-ons makes Firefox a versatile tool and makes it very valuable.
• Of course new browsers get a lot of use in the market, and so Google Chrome and Apple Safari (both WebKit-based browsers) are required arsenal. While these browsers are built on the same rendering engine, their other internals are very different. Google and Apple are always trying to better the Web. A lot of people use these browsers also because of their stability and relatively high performance.
• And finally the Opera Browser though not always of high use is an important asset. Out of the box it comes with Dragonfly, which is similar in functionality and purpose to Firebug. It also provides for another rendering standard, and Opera Mini is an important browser on the mobile platform, and uses the same rendering engine.

Automation

This next set of tools is a set of web testing tools that may or may not require a browser. Most of them I have used, some I have not used or haven't used very much, but their purpose is something I think highly of.

Automation: Browser-based

Browser-based automation tools come in at least two varieties. The first variety uses a browser like a Microsoft OLE (Object Linking and Embedding) object and the second utilizes the browser's core functionality to automate web-based testing.

Automation: Browser-based: OLE-type

• Under free software licensing we've got several options. Python has a library named PyWinAuto for Windows that grabs a connection to the OLE server for Internet Explorer. The library then exposes the OLE API as a simpler Python API that can be used to control the browser.
• Similarly, Ruby supports a system of grabbing a connection to Internet Explorer's OLE server and Watir (pronounced like "water") exposes this in a Ruby-based API. Watir's API is built in a familiar fashion such that people migrating from HP's QuickTest Pro web testing suite can grasp the concepts readily. Watir also has counterparts for other browsers, which are named for the browsers they support, such as FireWatir, ChromeWatir, and SafariWatir. Work is being done to integrate these all into a single codebase. Currently only FireWatir is integrated, and Watir uses a factory to determine which browser to launch. Firefox's only requirement is the JSSH (JavaScript SHell) extension which can be downloaded at the FireWatir page.
• Finally .NET got its feet wet in this arena also with WatiN, which is loosely based on the API of Watir and thus follows some of the same conventions. Its licensing allows for free download, but modifications and additions are supported through paid support. The source is freely available and the licensing also supports personal (for business or private) modifications. The advantage of WatiN is in the .NET - if your testers know C# better than Ruby then it's a plus.

While there are probably more, they aren't likely to be as highly developed.

Automation: Browser-based: Browser-Type

Browser-type automation toolkits utilize a browser's core internal functionality. They may be browser extensions or they might use JavaScript to control suites of unit-like tests. Because of this some of these tools are inherently browser- and operating-system-independent.

• The first on my list is the iMacros browser extension for Firefox. iMacros allows a user of the Firefox browser to record a series of steps taken on a webpage and then play it back at any time. You can also add in validations for particular elements on a web page. It appears as though Chrome also has an iMacros extension now. In order to use it, you will need to download and install the beta or developer branch for Chrome. Because this is a browser extension for specific browsers it is not browser- and operating-system-independent.
• Next on my list is Selenium. Selenium comes in several flavors. The most independent variant is Selenium Core. Selenium core is an HTML-JavaScript-based testing system which utilizes frames to automate your website and validate various points on it. Because of HTTP security protocols, Selenium Core must be installed next to your website and be accessed under the same domain. So normally you would probably not use this solution to test a web site in a production environment. Selenium RC or Selenium Remote Control on the other hand still utilizes the browser but creates a proxy to your site through a browser that uses Selenium Core to run tests outside of the actual domain. This means that no testing code resides on your server, but you still get the same effect. Selenium is highly developed and highly supported. There are several other offerings from Selenium HQ as well.

There are other tools that fall under this category, but these two are the best. And with Selenium's vast offerings, I don't think you could go wrong.

Automation: HTTP-based

HTTP-based automation of the web sites offers some speed and simplicity to the mix. There is no reliance on browsers whether they are buggy or not and whether they fully support JavaScript or not. On the other hand, HTTP-base testing solutions generally don't support JavaScript, so if your site relies heavily on it then this may not be what you're looking for. I have successfully used HTTP-based testing solutions to test web services, most static and dynamically generated web pages, and XML and RSS products. Here are a few of those products.

• HttpUnit is the first tool on this list. It is written in Java so generally speaking you can use it on any operating system as long as Java is supported by the operating system. HttpUnit goes about web-based testing like a series of unit tests based on the xUnit testing pattern. Generally you would use a third-party xUnit library to build your tests on, such as JUnit, then you would also use that library to run the tests. Unit testing utilizes the assertion pattern which means you assert a condition to be true, like an element that exists.
• HtmlUnit is another offering, again written in Java. The major difference between HttpUnit and HtmlUnit is that HtmlUnit allows you to test JavaScript. It sandboxes the JavaScript in a website similar to the way a browser does it, but it still remains headless and keeps the browser reliance low and the portability and stability high.
• HGrep is one of my own tools that I developed because sometimes I just wanted to know about headers and see things faster than a browser could provide them for me. Again it is a headless tool that I have successfully used to write automation. The tool itself does not provide any automation hooks, but scripts can be easily written in PowerShell which utilize HGrep for automation.
• Apache's JMeter is a load testing tool for the Web. It specifically focuses on HTTP-based testing and can read and write to SOAP, LDAP, JMS, POP and IMAP mail and regular HTTP protocols.

This gives you a good variety of web application testing tools. These are all highly developed and I recommend them all. If you have any other favorites, please feel free to post them here. Thanks.

As I continually program throughout my career and daily life, I come across the problem often that there are simply too many ways to program a system. The other problem is that there really isn't much of a correct way to program any specific system. It seems that the means to an end often involves trends. To clarify, I have been trying to program a decent text-based calculator for some time now. I began in Java and moved to .NET because it was a little bit simpler and higher level for me. I'll likely go back to Java simply because it suits my needs a little better, whereas I need a tool that can run anywhere. Let me backtrack a little. Since my first attempt at the calculator, it has seen at least six incarnations, two as a Java application and four as a .NET application.

1. My first attempt involved simply trying to parse out numbers and symbols, transform them into tokens, and finally using the Shunting-yard algorithm, solve the given equation. That first attempt failed miserably, and I actually got feedback on it to prove it. One of my biggest problems was, has been, and likely will always be negation, though it isn't much of a problem now, it always looms as an issue to be resolved late in the development cycle (usually last after completing the basic system).
2. My second attempt was to try and do the same thing in .NET only do it a little better (usually when you redo something, you try and learn from your initial mistakes and do better). This time I thought more about something that one of my contacts said I should try, namely using regular expressions. I also though I'd use Linq to see if I could make it work. Basically I used regular expressions to see what was coming next in the expression and to remove the next item from the original expression. I (like in the first attempt) first turned the whole string into an array of chars. So when I was looking for tokens like numbers, I was reconstructing the number from individual characters. Ultimately I ended up with two clunky types: a Posfixator class, which also parsed the expression, and an Evaluator class, which took the postfixated expression and evaluated it for an answer. Some of the difficulties I had with this incarnation included parentheses and functions. One very difficult thing was implementing multiple-argument functions, like Power (defined in many languages as Math.Power(double x, double y)). I had reserved the comma for that purpose, but it wasn't really working.
3. The third attempt to make a good calculator involved going back to Java. The reason for this was to try and get the low-level concepts clarified. Since Java doesn't have frameworks like Linq, and its enumerable framework isn't quite as developed (in my opinion, or at least it has taken a different route from .NET), I thought the challenge would help me figure out where I could improve. I continued to use the idea of regular expressions to match patterns at the beginning (left side) of the expression and remove those bits from the expression, but this time I thought, why do I need to break the expression down into an array of chars, and why do I need to process whitespace? So I got rid of whitespace in the expression before tokenizing it, and left it as a string. The result was a little bit cleaner.
4. Right away I went back to .NET to fully clean up the design and followed the same pattern of first removing whitespace and then upon finding tokens based on regular expressions, removing them from the expression to be evaluated. This time I also decided to separate all of the possible tokens into their own classes that contained their regular expressions. It served to be a very manageable system, while at the same time it felt somewhat cluttered to have 28 classes all in a single project. I also started to work on the idea of having matrices and variables in the system. That required making a State class to keep track of the internal heap. I perfected [at least as much as I could] the notion of negative numbers, in that I kept track of the last token I read and if it was either nothing or a number then the hyphen was a subtraction symbol, but if I read a parenthesis or another operator, then I was pretty certain that I was dealing with negation. Then I would set myself up to negate the next number. That worked very well. I still had the function problem, and didn't find a way to resolve it at that point.
5. My fifth attempt took a wild turn. With all of this experience behind me I determined to figure out whether using regular expressions more would be worthwhile. I remained in .NET this time. I decided that I would use recursion and regular expressions to evaluate sub-expressions hierarchically and then instead of needing to worry about postfixation of the tokens, I would be able to immediately know the answers to individual complete components of the whole. This worked out very well in the end. I had a couple of giant regular expression to test for things like decimal and hexadecimal numbers, sub-expressions defined by what was contained in parentheses, and about this time I had discovered Perl more intimately, which has its own operator for the power function, **. I immediately included it in my own evaluation, and didn't have to worry too much anymore about multiple-argument functions. I also used regular expressions to find functions quickly and knowingly evaluate their contents first, and then them. I overcame a lot of previous hurdles in this attempt, however it ultimately was just a learning session. The regular-expression-recursion-based calculator, the one I had initially wanted to use, but didn't know how to do it just yet, turned out to be a flop. The evaluation of simple expressions such as

   24 + 12

   were taking far too long. I thought I had reduced complexity a little, by getting rid of the Shunting-yard algorithm altogether, and by evaluating the expression immediately rather than using lazy evaluation. I mentioned these facts about this particular incarnation of the calculator in my previous post. So I decided that I needed to try again to make a text-based calculator tool that I would be able to use on a daily basis that would be relatively fast and simple in design and structure as well. I wanted to ensure that it would be easy to add new functionality to it, and that I could prove its correctness.
6. Enter sixth incarnation of Personal Calculator. The latest and truly greatest attempt for the personal calculator was somewhat inspired by another project, totally unrelated to calculators at all that I happened to notice in my Visual Studio RSS Feed Reader.

   Introducing Elevate. Elevate is a Boost-like library fot .NET that features many utilities and high performance tools that may be of value to developers.

   I didn't really know what Boost was, and I thought, "what can it hurt? I'll take a look." So I did, and I found something in Elevate that I really liked. Elevate is an extension project for .NET to extend class to have the utilities that make programming easier and more sensible in other languages, like Ruby's "everything is an object" mentality. Or Haskell's Currying. Instantly I thought about how I had done parsing in the past to pull tokens from a mathematical expression using regular expressions. And I thought about the real differences between the new String.Split methods used in many languages and the old StringTokenizer class in Java. That class never really did what I expected it to, as all it does is provide a class to create an enumerable collection of tokens from a string using a delimiter. Isn't that what String.Split does? So I created a string extension method for .NET that tokenized the current string based on an array of regular expressions. It would follow the same pattern as the fourth and third attempts at parsing to tokenize a string, by looking for specific tokens at the beginning of the string and then removing the whole token upon finding them. This wouldn't differentiate between certain types of tokens though, that would be done later in the calculator. It worked like a charm. Here is the implementation:

   public static string[] Tokenize(this string s, string[] patterns)
   {
       List tokens = new List();
       bool noMatchesFound = false;
       while (!String.IsNullOrEmpty(s) && !noMatchesFound)
       {
           for(int index = 0; index <>
           {
               Regex pattern = new Regex(patterns[index]);
               if (pattern.IsMatch(s))
               {
                   string match = pattern.Matches(s)[0].Value;
                   tokens.Add(match);
                   s = s.Substring(match.Length);
                   index = -1;
               }
   
               if (index == patterns.Length - 1)
               {
                   noMatchesFound = true;
               }
           }
       }
   
       return tokens.ToArray();
   }

   And here is an example of usage:

   string[] tokens = expression.Tokenize(new string[] {
       "^[\\d]+([.]{1}[\\d]+){0,1}",
       "^[-]{0,1}[\\d]+([.]{1}[\\d]+){0,1}",
       "^[+]{1}",
       "^[-]{1}",
       "^(\\*\\*){1}",
       "^[*]{1}",
       "^[/]{1}"
   });

   In all this worked out great on reducing complexity in the calculator because I didn't have to worry about tokenizing anymore. Then I could focus on evaluation, which would still require the Shunting-yard algorithm, but I already knew that my implementation was relatively fast, and I still didn't really need to keep track of token types, because I could always look them up, which in a hashtable is a 1-1 relationship and O1 is all of the processor time I'd need for that.

As you can see I haven't gotten to implementing parentheses or functions yet in this version, but it only took me six hours to write it. And I've been able to abstract a good portion of the program out into a separate project that I call Nathandelane.System. I am also now able to accept command-line arguments to set the initial state of the calculator. Also my classes or more acceptable: Calculator which contains state and pattern matching, ExpressionEvaluator which puts the expression into postfix format and evaluates it, PrecedenceMap which defines precedence for operators and functions, TokenPatterns which defines all of the patterns for individual tokens, and TokenType which is a simple enumeration to keep track of the token type during evaluation. So with six different methods of conquering the same task, some of them worked better than others, some were more complex than others, some of them ended up taking more processing power than others. I guess programming boils down to experience. I have learned a lot doing this project. I probably would have done better if I had based my project fully on somebody else's project. If I could extract common patterns to use that make sense, which I have then I could also provide a better outcome in the end.

A while back I determined that I wanted an easy to use text-mode calculator that could perform all of the calculations I required in my job as a web programmer. Often these are simple arithmetic. As I set out to write my first calculator that was more than a simple GUI with buttons to click, I began asking questions about the best method to use in the process. I already knew about postfix notation, which is where you introduce operands first and the function last, as in

384 1024 +

This is the addition function with the two operands 384 and 1024 for its left and right. In standard mathematical infix notation this would simply look like 384 + 1024. To get from infix to postfix notation, the simplest method is to use what is known as the Shunting-yard Algorithm. This algorithm takes all of the tokens of a mathematical equation and divides them into four (or more) types: operators/functions, numbers, function operand separators (commas), and parentheses. Using these tokens the algorithm puts operators and functions in one stack and numbers in another stack. Ultimately what comes out is a hierarchical tree representing the expression given as input that can now be parsed linearly to produce a correct result. As an example take the following infix expression:

-(32 + 12) * 19 / 3 + (-1 * 92)

When converted to postfix format, the expression would appear as follows:

32 12 + - 19 * 3 / -1 92 * +

You begin to evaluate this then from left to right, first gathering arguments and then operators. I list the operations.

1. Put 32 into a stack
2. Put 12 into a stack
3. Found +, pop two numbers from the stack, right = 12, left = 32, and add them
4. Put 44 into a stack
5. Found -, try to pop two number, but found one, so this is a negation, then negate 44
6. Put -44 into a stack
7. Put 19 into a stack
8. Found *, pop two numbers from the stack, right = 19, left = -44, and multiply them
9. Put -836 into a stack
10. Put 3 into a stack
11. Found /, pop two numbers from the stack, right = 3, left = -836, and divide them
12. Put -278.66 into a stack
13. Put -1 into a stack
14. Put 92 into a stack
15. Found *, pop two numbers from the stack, right = 92, left = -1, and multiply them
16. Put -92 into a stack
17. Found +, pop two numbers from the stack, right = -92, left = -278.66, and add them
18. Put -370.66 into a stack
19. Nothing else to evaluate, so pop the only number on the stack, -370.66 is your answer

Just for the sake of checking the answer:

1. -(32 + 12) * 19 / 3 + (-1 * 92)
2. -44 * 19 / 3 + -92
3. -836 / 3 + -92
4. -278.66 + -92
5. -370.66

Fewer operations to do it by hand, but we end up with the same answer. So it works. My first few attempts at creating my calculator relied on this method of solving mathematical expressions. I wrote one in Java, and one in C#, and both were fast and efficient. One of the people I talked to suggested I try evaluating using regular expressions. So most recently I took on the challenge. I downloaded myself a decent regular expression tester (RegExr), and began working on what makes up each of the tokens. I would then extract the tokens based on their matches. In the first method I also used regular expressions to find numbers, functions and operators, but I only had to know about each token individually. The case with the regular expression based calculator would be that I would focus on expression snippets or sub-expressions. First I went to the regexp that I had originally used to define a number:

[\d.]+

I found that this was not exactly accurate, because with it I could have numbers like 24.1.0 or .1.1.1.2, which are not valid decimal values. So I dug a little deeper and came up with:

(([-]{0,1}[\d]+([.]{0,1}[\d]+){0,1})([d]{0,1}))

The individual components of a decimal number are first, the possibility of it starting with a negative sign [-]{0,1} then one or more digits [\d]+ possibly followed by a decimal and then one or more digits again ([.]{0,1}[\d]+){0,1} and then I added the possibility that you could suffix your number with the letter d. So the following values would be correct decimal numbers:

• 1
• -1
• 24
• 19
• 236
• 1.12
• 0.98
• 20d
• 3.1412356487897

I didn't want to allow for commas because I wanted to reserve commas for function operand separators in case I had a function that would take more than a single value (like trig functions). I then set out defining the most basic arithmetic operator patterns including numbers. I will refer to the pattern for decimal numbers by the letter n. I came up with the following patterns:

• Addition, n([+]{1})n
• Subtraction, n([-]{1})n
• Multiplication, n([*]{1})n
• Division, n([/]{1})n
• Power, n((\*\*){1})n
• XOR, n([^]{1})n
• Modulus, n([%]{1})n
• AND, n([&]{1})n
• OR, n([|]{1})n

To shorten this process I combined all of the operators together to look for arithmetic sub-expressions and then determined order of operations after that. This sort of evaluation allowed me to evaluate chunks of the expression one time. With the Shunting-yard algorithm I had to find all of the tokens first and put them in the correct order, and then evaluate them. With the regular expression algorithm I was able to evaluate recursively. The one downfall of the regular expression algorithm, even though it was cool, is that it generally takes five or more times longer to evaluate simple expressions:

• Regular Expression algorithm, 24 + 12, five seconds
• Shunting-yard algorithm, 24 + 12, less than one second

What have I learned? Without digging deeply into the possibility that recursion is to blame,

1. Regular expressions tend to be more efficient at locating sub-expressions
2. Evaluating once by regular expressions tends to be slower than parsing once and evaluating once
3. Complexity of the regular expression algorithm was lower because of recursion (almost a recursion anti-pattern, because recursion is generally more complex)
4. Shunting-yard algorithm seems to have been time tested and well thought out
5. Regular expression algorithm took a long time to find large regular expressions like the sub-expression regular expression, shown here: ([\(]{1})((([-]{0,1}[\dABCDEF]+)([h]{1}))|(([-]{0,1}[\d]+([.]{0,1}[\d]+){0,1})([d]{0,1}))|(([-]{0,1}[01234567]+)([o]{1}))|(([-]{0,1}[01]+)([b]{1}))|((\*\*|[+-/*\(\)^%&|]){1})|([-]{0,1}(e|pi|\$){1})|(([-]{0,1}([bdho]|cos|sin|tan){1})([\(]{1})((([-]{0,1}[\dABCDEF]+)([h]{1}))|(([-]{0,1}[\d]+([.]{0,1}[\d]+){0,1})([d]{0,1}))|(([-]{0,1}[01234567]+)([o]{1}))|(([-]{0,1}[01]+)([b]{1}))|((\*\*|[+-/*\(\)^%&|]){1})|([-]{0,1}([bdho]{1}|cos|sin|tan){1})|([-]{0,1}(e|pi|\$){1}))+([\)]{1})))+([\)]{1}) Nice, huh!

I have written four different calculators using Java and C#, and I have found that both languages handle both algorithms equally well. I have found several different ways to do the Shunting-yard algorithm that are satisfactory, and one way to do the Regular Expression algorithm well, but found it to be significantly slow. So what's next? I think I'm going to try using something like Shunting-yard to do prefix based calculations. Whether there is already a name for that, I don't know. Finding the most clean and minimal method of using the Shunting-yard algorithm is still beyond me. With my second Shunting-yard calculator (first C# calculator), I found that creating a class for each token worked out well, but with the Regular Expression calculator I found that I really didn't need to keep track of tokens, I just injected solutions to sub-expressions into the original expression and re-evaluated. Cheers.