We are accustomed to the 'infix' system of mathematical notation, as in '2+2', 'a*b-c', etc. There are two alternatives to placing the operators between the operands: one is to place the operator in front of its two operands (known as 'prefix'); the other is to place the operator after its two operands (known as 'postfix').
In prefix '2+2' becomes '+2 2'; in postfix it becomes '2 2+'.
Prefix is not much used but postfix is important in computing because it is, in fact, the way that the arithmetic and logic unit (ALU) inside a CPU works. A program must present two operands to the ALU before it can perform an arithmetic or logical operation on them, such as add or and. (Could it be that this is the way the brain works too: there must be two operands before the brain can operate on them.)
One of the tasks of a compiler, therefore, is to convert the infix notation of programmers into the postfix order that the ALU can process. The program presented here does not produce the answers to expressions, only the converted notation in string form, but it's a start.
Some computer languages include postfix notation as an option (Logo, for example) and early calculators (notably those from HP) required input in postfix.
It was a Polish logician called Jan Lukasiewicz (hence the name 'Reverse Polish') who noticed that brackets were not required in postfix (or prefix) notation in order to guarantee correct observation of operator precedence. In standard infix notation the expressions 'a*b+c' and 'a*(b+c)' have different outcomes but in postfix brackets are not required.
The postfix form of 'a*(b+c)' is: abc+*. This is evaluated by proceeding to the first operator (+) and applying to the two preceding operands; this makes a new operand (the result of b+c); the next operator is * and its operands are b+c and a. Analysis of postfix expressions is often done by underlining the operator-operands triplet:
abc+* and ad* (where d = b+c)
There are at least two ways to convert infix to postfix, one involving a binary tree structure and the other a stack. It happens that, if an expression is entered into a binary tree with the operators in parent nodes and the operands in child leaves (with no further links) the resulting tree structure can be traversed in the three standard ways to produce the three forms of expressions: inorder traversal gives an infix expression; preorder traversal gives prefix notation; and postorder traversal gives postfix notation. Try this with the following:
*
/ \
+ c
/ \
a b
The second way to convert between infix and postfix is the one followed here, using a stack. Operators are placed on a stack and popped from it into the postfix expression according to their precedence.
For the program we create a form:
We make some declarations in the public section of the form class:
stack:array[1..50] of char;
expression:string;
rpnexpression:string;
Note that the stack is declared as an array of characters rather than as a string; this is so that the notation stack[top] can be used to access individual elements.
The algorithm we are seeking to implement in code is as follows:
Note that this algorithm provides an example of a push-down automaton, a simple model of a computer that includes a stack; the top of the stack can be used to determine the next transition and can manipulate the stack when performing a transition.
The work is done by the Convert button:
procedure TForm1.Button1Click(Sender: TObject);
procedure convertToRPN(expression:string; var rpnexpression:string);
var
i, top:integer;
symbol, tempsymbol:char;
function priority(operator:char):integer;
begin
case operator of
'(': priority:= 0;
'+','-': priority:= 1;
'*','/': priority:= 2;
end;
end;
procedure pop(var top:integer; var element:char);
begin
if top=0 then showmessage('Stack empty')
else
begin
element:=stack[top];
dec(top);
end;
end;
procedure push(var top:integer; element:char);
begin
if top >= stacklimit then showmessage('Stack full')
else
begin
inc(top);
stack[top]:=element;
end
end;
begin //convertToRPN
top:=0;
rpnexpression:='';
for i:= 1 to length(expression) do
begin
symbol:=expression[i]; //next
token
if not (symbol=' ') then //discard
blanks
if symbol = '(' then
//left bracket so push on stack
push(top,symbol)
else if symbol=')' then
//right bracket so pop stack until left bracket
begin
while not (stack[top]='(') do
begin
pop(top,symbol);
rpnexpression:=rpnexpression+symbol;
//showmessage('removing inside
brackets' + symbol);
end;
pop(top,symbol);
//remove '('
//showmessage('removing outside
brackets' + symbol);
end
else if symbol in ['+','-','*','/'] then
//operator
begin
while not (top=0) and (priority(symbol) <= priority(stack[top])) do
//stack not empty; compare operator priorities
begin
pop(top,tempsymbol); //get
operator from stack but don't overwrite current symbol
rpnexpression:=rpnexpression+tempsymbol;
//add operator to expression
end;
push(top,symbol);
//push operator symbol anyway
end
else
rpnexpression:=rpnexpression+symbol;
//if conditions fail, stack empty or priorities then add operator to expression
end; //for
while not (top =0) do //pop stack
to expression
begin
pop(top,symbol);
rpnexpression:=rpnexpression+symbol;
end;
end;
begin //Button1Click
convertToRPN (edit1.text, rpnexpression);
//rpnexpression returned by var parameter
edit2.Text:=rpnexpression;
end;
The comments should explain the program logic and mechanism.
We can make a better job of this program by employing some object oriented techniques. Instead of placing the procedures for manipulating the stack and generating the postfix expression inside the ButtonClick procedure we can create a class for the object and thus make its fields and members available to the rest of the program. When the procedures are declared inside the ButtonClick procedure they are, because of the rules of scope, only visible from within ButtonClick. By placing them in a class in the unit we can make them available to the unit as a whole and also to other units that want to use the class and its methods.
To begin this approach we define the stack as a class, simply by moving the elements of code we already have:
type
TStack=class(TObject)
stack:array[1..50] of char;
rpnexpression:string;
expression:string;
top:integer;
symbol,tempsymbol:char;
element:char;
procedure convertToRPN(expression:string);
function priority(operator:char):integer;
procedure pop(var top:integer; var element:char);
procedure push(var top:integer; element:char);
private
public
end; ...
var
Form1: TForm1;
rpnstack:Tstack;
We have now made the rpnstack object available to the rest of the unit so we can call its methods from inside the ButtonClick procedure instead of having to define them there as well:
procedure TForm1.Button1Click(Sender: TObject);
begin
rpnstack:=TStack.Create; //notice the form of
the create method
convertToRPN(edit1.text);
edit2.Text:=rpnstack.rpnexpression;
rpnstack.Free; //release memory taken by the
rpnstack object
end;
The only difference in the rest of the code is that the procedure name must be proceeded by the class name:
procedure TStack.pop(var top: integer; var element:
char);
procedure TStack.push(var top:integer; element:char);
function TStack.priority(operator: char): integer;
procedure TStack.convertToRPN(expression: string);
By adding unit1 to the uses clause the TStack class, its fields and properties can be accessed from another unit that wants to use them; they do not need to be redefined. (This is a relatively simple class with a fairly specialised application; this approach becomes more valuable as the classes become more general.)