Jolie Rouge

all ur parentheses Я belong to me

Parsing infix to postfix in C++11

Pursuant to my interest in programming language design, I have been giving a lot of thought to mathematical expressions. Making sense of a mathematical expression written by a human is difficult from an algorithmic point of view. It’s certainly not impossible.

Humans read and write mathematical expressions in a notation called infix1  however this requires sorting operators by precedence2, which humans are very good at, but computers not so much. To be able to do it, a computer has to first parse and identify all parts of a token stream until the end, and then group those parts, and then sort them based on the operator precedence. That’s an awful lot of work. There is however another type of notation[actually there are several.] called postfix3 which is very easy for a computer to operate on because each time it encounters an operator4 it simply collapses the last two numbers and replaces the operator with the answer. In this way the token stack reduces to a single number by a series of linear actions requiring no lookahead5 or knowledge of what is to come.

I decided today to implement a mini calculator language that takes an infix expression6 and returns the value after parsing it into postfix to operate on it.

Here is the code:


clang++ and C++11 generic Makefile

As a general rule, I have a little scratch pad Makefile that I use as a template for all my C++ apps. I thought I would post my basic template when I am prototyping some code, or just running a little test example.

FLAGS=-std=c++11 -stdlib=libc++


clang++, libc++ on Kubuntu (c++11, c++0x) Compiling and Linking

This is what I did to compile the latest Clang on Kubunut (AKA Kuboobtu).


First things first. You’ll need to download llvm. You may need to set permissions on /usr/local/src

sud apt-get install gcc g++ subversion
cd /usr/local/src
svn co llvm