Howdy, Stranger!

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

Categories

Help with a program infix to RPN

bimlabimla Member Posts: 4
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

  • Phat NatPhat Nat Member Posts: 757
    : 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.