Help with a program infix to RPN

I need an insight as to what I could possibly be doing wrong, any assistance given would be greatly appreciated.

I wrote a program to convert an infix expression to RPN using arrays of stacks and queues. I have to convert it to use pointers instead of arrays but I got a bit stuck, the program is compiling but it is not running as it should. Whenever brackets are entered as a part of the infix expression, it goes into an infinite loop.

PROGRAM InfixToRPN;

CONST
max = 50;

TYPE
link = ^node;
node = record
data :char;
next: link
end;

stack = record
top : link
end;

queue = record
front, rear : link
end;


Expression = ARRAY [1..Max] of char;
CharacterSet = SET OF char;

VAR
Exp : Expression;
Length : integer;
OperatorSet : CharacterSet;
Symb, answer : char;
Oper, infix: stack;
q : link;
qu: queue;

FUNCTION Priority (operator : char) : integer;
BEGIN
CASE OPERATOR of
'(' : Priority := 0;
'+', '-': Priority := 1;
'*', '/' : Priority := 2
END
END;

PROCEDURE Initialise (Var Q: queue);
{Pre: The array that is being used by the user
Post: The user can now operate on an empty array}
Begin
Q.front := nil;
Q.rear := nil;
End;


PROCEDURE Enqueue (VAr pt:link; Var Q: queue; x: char);
{Pre: The array that is being used
Post: The updated array with the character that has been entered}
{Var pt: link;}
Begin
If Q.rear = nil then
Begin
New (Q.rear);
Q.front := Q.rear;
End
else
Begin
New (Q.rear^.next);
Q.rear := (Q.rear^.next)
End;
Q.rear^.data := x;
Q.rear^.next := nil;
End;


PROCEDURE InitialiseS (var S: stack);
{Pre: The stack that is being used by the user
Post: The user can now operate on an empty stack}
Begin
S.top := nil;
End;

FUNCTION Empty (Var S: Stack) : boolean;
{Pre: The stack that is being used
Post: The response as to whether the stack is empty or not}
Begin
Empty := (S.top = nil)
End;

PROCEDURE Push (VAR S: stack; x: char);
{Pre: The stack that is being used
Post: The updated stack with the character that has been entered}
VAR pt : link;
Begin
New (pt);
pt^.data := x;
pt^.next := S.top;
S.top := pt;
End;


PROCEDURE Pop (VAr pt:link; VAR S: Stack; VAr x: char);
{Pre: The stack that is being used
Post: The updated stack without the last character entered}
Begin
If not Empty(S) then
Begin
x:= S.top^.data;
pt := S.top;
Writeln;
S.top := S.top^.next;
Dispose (pt)
End
Else writeln ('Sorry, the stack is empty!');
End;



PROCEDURE ExpToInf (Var Infix: stack; Var x : char; Exp :Expression; length:integer);
Var i : integer;

Begin
InitialiseS (infix);
For i := length downto 1 do
begin
x := exp[i];
push (infix, x)
end
End;

PROCEDURE ConvertToRPN (VAr pt:link;Var Inf : stack; Var Symbol: char; Exp: Expression; Length: integer;
OperatorSet: CharacterSet);

VAR
Oper: Stack;
i, j : integer;
TempSymbol : char;
Qu: queue;
{pt: link;}

BEGIN
InitialiseS (oper);
Initialise (qu);
While Not Empty(inf) do
begin
Pop (q, Inf, symbol);
If Symbol <> ' ' then
If symbol = '(' then
Push (oper, symbol)
else if symbol = ')' then
begin
while pt^.data <> '(' do
begin
pop (pt, oper, symbol);
enqueue (pt, qu, symbol)
end;
pop (pt, oper, symbol);
end
else if symbol IN operatorset then
begin
while Not Empty (oper) and
(Priority (symbol) <= Priority (pt^.data)) do
begin
pop (pt, oper, tempsymbol);
enqueue(pt, qu, tempsymbol);
end;
Push (oper, symbol)
end
else
enqueue (pt, qu, symbol)
end;
while Not Empty (oper) do
begin
pop(pt, oper, symbol);
enqueue (pt, qu, symbol);
end;
pt:= Qu.front;
While pt <> nil do
Begin
Write (pt^.data, ' ');
pt := pt^.next;
end;

end;

BEGIN {MAIN}
OperatorSet := ['+', '-', '*','/'];
Repeat
Writeln ('***** Welcome to the Converter! *****');
Writeln;
Write ('Enter the infix expression: ');
Length := 0;
While not eoln do
begin
length := Length + 1;
read (Exp[Length])
end;
readln;
writeln;
write ('The RPN Expression is : ');
ExpToInf(Infix, symb, Exp, length);
ConvertToRPN (q, Infix, Symb, Exp, Length, OperatorSet);
Writeln;
Writeln ('Would you like to do another?');
Writeln;
Write ('Type Y to continue: ');
Readln (answer);
writeln;
Until not (answer in ['y', 'Y']);
Writeln ('Thank you for using the converter! Goodbye!');
Readln;
Writeln;
Writeln;
End.

Comments

  • : I need an insight as to what I could possibly be doing wrong, any assistance given would be greatly appreciated.
    :
    : I wrote a program to convert an infix expression to RPN using arrays of stacks and queues. I have to convert it to use pointers instead of arrays but I got a bit stuck, the program is compiling but it is not running as it should. Whenever brackets are entered as a part of the infix expression, it goes into an infinite loop.

    [code]
    : PROGRAM InfixToRPN;
    :
    : CONST
    : max = 50;
    :
    : TYPE
    : link = ^node;
    : node = record
    : data :char;
    : next: link
    : end;
    :
    : stack = record
    : top : link
    : end;
    :
    : queue = record
    : front, rear : link
    : end;
    :
    :
    : Expression = ARRAY [1..Max] of char;
    : CharacterSet = SET OF char;
    :
    : VAR
    : Exp : Expression;
    : Length : integer;
    : OperatorSet : CharacterSet;
    : Symb, answer : char;
    : Oper, infix: stack;
    : q : link;
    : qu: queue;
    :
    : FUNCTION Priority (operator : char) : integer;
    : BEGIN
    : CASE OPERATOR of
    : '(' : Priority := 0;
    : '+', '-': Priority := 1;
    : '*', '/' : Priority := 2
    : END
    : END;
    :
    : PROCEDURE Initialise (Var Q: queue);
    : {Pre: The array that is being used by the user
    : Post: The user can now operate on an empty array}
    : Begin
    : Q.front := nil;
    : Q.rear := nil;
    : End;
    :
    :
    : PROCEDURE Enqueue (VAr pt:link; Var Q: queue; x: char);
    : {Pre: The array that is being used
    : Post: The updated array with the character that has been entered}
    : {Var pt: link;}
    : Begin
    : If Q.rear = nil then
    : Begin
    : New (Q.rear);
    : Q.front := Q.rear;
    : End
    : else
    : Begin
    : New (Q.rear^.next);
    : Q.rear := (Q.rear^.next)
    : End;
    : Q.rear^.data := x;
    : Q.rear^.next := nil;
    : End;
    :
    :
    : PROCEDURE InitialiseS (var S: stack);
    : {Pre: The stack that is being used by the user
    : Post: The user can now operate on an empty stack}
    : Begin
    : S.top := nil;
    : End;
    :
    : FUNCTION Empty (Var S: Stack) : boolean;
    : {Pre: The stack that is being used
    : Post: The response as to whether the stack is empty or not}
    : Begin
    : Empty := (S.top = nil)
    : End;
    :
    : PROCEDURE Push (VAR S: stack; x: char);
    : {Pre: The stack that is being used
    : Post: The updated stack with the character that has been entered}
    : VAR pt : link;
    : Begin
    : New (pt);
    : pt^.data := x;
    : pt^.next := S.top;
    : S.top := pt;
    : End;
    :
    :
    : PROCEDURE Pop (VAr pt:link; VAR S: Stack; VAr x: char);
    : {Pre: The stack that is being used
    : Post: The updated stack without the last character entered}
    : Begin
    : If not Empty(S) then
    : Begin
    : x:= S.top^.data;
    : pt := S.top;
    : Writeln;
    : S.top := S.top^.next;
    : Dispose (pt)
    : End
    : Else writeln ('Sorry, the stack is empty!');
    : End;
    :
    :
    :
    : PROCEDURE ExpToInf (Var Infix: stack; Var x : char; Exp :Expression; length:integer);
    : Var i : integer;
    :
    : Begin
    : InitialiseS (infix);
    : For i := length downto 1 do
    : begin
    : x := exp[i];
    : push (infix, x)
    : end
    : End;
    :
    : PROCEDURE ConvertToRPN (VAr pt:link;Var Inf : stack; Var Symbol: char; Exp: Expression; Length: integer;
    : OperatorSet: CharacterSet);
    :
    : VAR
    : Oper: Stack;
    : i, j : integer;
    : TempSymbol : char;
    : Qu: queue;
    : {pt: link;}
    :
    : BEGIN
    : InitialiseS (oper);
    : Initialise (qu);
    : While Not Empty(inf) do
    : begin
    : Pop (q, Inf, symbol);
    : If Symbol <> ' ' then
    : If symbol = '(' then
    : Push (oper, symbol)
    : else if symbol = ')' then
    : begin
    [b]: while pt^.data <> '(' do
    : begin
    : pop (pt, oper, symbol);
    : enqueue (pt, qu, symbol)
    : end;
    [/b]: pop (pt, oper, symbol);
    : end
    : else if symbol IN operatorset then
    : begin
    : while Not Empty (oper) and
    : (Priority (symbol) <= Priority (pt^.data)) do
    : begin
    : pop (pt, oper, tempsymbol);
    : enqueue(pt, qu, tempsymbol);
    : end;
    : Push (oper, symbol)
    : end
    : else
    : enqueue (pt, qu, symbol)
    : end;
    : while Not Empty (oper) do
    : begin
    : pop(pt, oper, symbol);
    : enqueue (pt, qu, symbol);
    : end;
    : pt:= Qu.front;
    : While pt <> nil do
    : Begin
    : Write (pt^.data, ' ');
    : pt := pt^.next;
    : end;
    :
    : end;
    :
    : BEGIN {MAIN}
    : OperatorSet := ['+', '-', '*','/'];
    : Repeat
    : Writeln ('***** Welcome to the Converter! *****');
    : Writeln;
    : Write ('Enter the infix expression: ');
    : Length := 0;
    : While not eoln do
    : begin
    : length := Length + 1;
    : read (Exp[Length])
    : end;
    : readln;
    : writeln;
    : write ('The RPN Expression is : ');
    : ExpToInf(Infix, symb, Exp, length);
    : ConvertToRPN (q, Infix, Symb, Exp, Length, OperatorSet);
    : Writeln;
    : Writeln ('Would you like to do another?');
    : Writeln;
    : Write ('Type Y to continue: ');
    : Readln (answer);
    : writeln;
    : Until not (answer in ['y', 'Y']);
    : Writeln ('Thank you for using the converter! Goodbye!');
    : Readln;
    : Writeln;
    : Writeln;
    : End.
    [/code]

    I hilighted where your program goes into the loop. It loops until it finds a "(", but it empties the stack before then. You need to add a check for an empty stack, such as
    [b]while (pt^.data <> '(') AND (Oper^.Top = nil) do[/b]
    however, things are still mis-ordered.
    The easiest way to convert is to only push operators and brackets onto the stack and directly output the numerals/characters to the screen. When a closing bracket is encountered, pop off all the symbols until the opening bracket is found.

    Hope this helps,
    Phat Nat

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion