Anonymous user
Arithmetic evaluation: Difference between revisions
Ada example
(Ada example) |
|||
Line 7:
*Multiplication/Division (left to right)
*Addition/Subtraction (left to right)
=={{header|Ada}}==
This example is produced in several packages. The first package provides a simple generic stack implementation employing a controlled type. Controlled types are automatically finalized during assignment and when the variable goes out of scope.
with Ada.Finalization;
generic
type Element_Type is private;
with function Image(Item : Element_Type) return String;
package Generic_Controlled_Stack is
type Stack is tagged private;
procedure Push(Onto : in out Stack; Item : Element_Type);
procedure Pop(From : in out Stack; Item : out Element_Type);
function Top(Item : Stack) return Element_Type;
function Depth(Item : Stack) return Natural;
procedure Print(Item : Stack);
Stack_Empty_Error : exception;
private
type Node;
type Node_Access is access Node;
type Node is record
Value : Element_Type;
Next : Node_Access := null;
end record;
type Stack is new Ada.Finalization.Controlled with record
Top : Node_Access := null;
Count : Natural := 0;
end record;
procedure Finalize(Object : in out Stack);
end Generic_Controlled_Stack;
The type Ada.Finalization.Controlled is an abstract type. The Finalize procedure is overridden in this example to provide automatic clean up of all dynamically allocated elements in the stack. The implementation of the package follows:
with Ada.Unchecked_Deallocation;
with Ada.Text_IO; use Ada.Text_IO;
package body Generic_Controlled_Stack is
procedure Free is new Ada.Unchecked_Deallocation(Node, Node_Access);
----------
-- Push --
----------
procedure Push (Onto : in out Stack; Item : Element_Type) is
Temp : Node_Access := new Node;
begin
Temp.Value := Item;
Temp.Next := Onto.Top;
Onto.Top := Temp;
Onto.Count := Onto.Count + 1;
end Push;
---------
-- Pop --
---------
procedure Pop (From : in out Stack; Item : out Element_Type) is
temp : Node_Access := From.Top;
begin
if From.Count = 0 then
raise Stack_Empty_Error;
end if;
Item := Temp.Value;
From.Count := From.Count - 1;
From.Top := Temp.Next;
Free(Temp);
end Pop;
-----------
-- Depth --
-----------
function Depth(Item : Stack) return Natural is
begin
return Item.Count;
end Depth;
---------
-- Top --
---------
function Top(Item : Stack) return Element_Type is
begin
if Item.Count = 0 then
raise Stack_Empty_Error;
end if;
return Item.Top.Value;
end Top;
-----------
-- Print --
-----------
procedure Print(Item : Stack) is
Temp : Node_Access := Item.Top;
begin
while Temp /= null loop
Put_Line(Image(Temp.Value));
Temp := Temp.Next;
end loop;
end Print;
--------------
-- Finalize --
--------------
procedure Finalize(Object : in out Stack) is
Temp : Node_Access := Object.Top;
begin
while Object.Top /= null loop
Object.Top := Object.Top.Next;
Free(Temp);
end loop;
Object.Count := 0;
end Finalize;
end Generic_Controlled_Stack;
The next little package gets the tokens for the arithmetic evaluator.
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
package Arithmetic_Tokens is
procedure Get_token(From : String;
Starting : Positive;
Token : out Unbounded_String;
End_Index : out Positive);
end Arithmetic_Tokens;
Again, the most interesting parts are in the package body.
package body Arithmetic_Tokens is
---------------
-- Get_token --
---------------
procedure Get_token (From : String;
Starting : Positive;
Token : out Unbounded_String;
End_Index : out Positive) is
Result : Unbounded_String := Null_Unbounded_String;
Is_Numeric : Boolean := False;
Found_Token : Boolean := False;
subtype Numeric_Char is Character range '0'..'9';
begin
End_Index := Starting;
if Starting <= From'Last then
loop -- find beginning of token
case From(End_Index) is
when Numeric_Char =>
Found_Token := True;
Is_Numeric := True;
when '(' | ')' =>
Found_Token := True;
when '*' | '/' | '+' | '-' =>
Found_Token := True;
when others =>
End_Index := End_Index + 1;
end case;
exit when Found_Token or End_Index > From'Last;
end loop;
if Found_Token then
if is_numeric then
while Is_Numeric loop
Append(Result, From(End_Index));
End_Index := End_Index + 1;
if End_Index > From'last or else From(End_Index) not in Numeric_Char then
Is_Numeric := False;
end if;
end loop;
else
Append(Result, From(End_Index));
End_Index := End_Index + 1;
end if;
end if;
end if;
Token := Result;
end Get_token;
end Arithmetic_Tokens;
Finally, we come to the arithmetic evaluator itself. This approach first converts the infix formula into a postfix formula. The calculations are performed on the postfix version.
with Ada.Text_Io; use Ada.Text_Io;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Generic_Controlled_Stack;
with Arithmetic_Tokens; use Arithmetic_Tokens;
procedure Arithmetic_Evaluator is
function Calculate(Expr : String) return Integer is
function To_Postfix(Expr : String) return String is
package String_Stack is new Generic_Controlled_Stack(Unbounded_String, To_String);
use String_Stack;
Postfix : Unbounded_String := Null_Unbounded_String;
S : Stack;
Token : Unbounded_String;
Temp : Unbounded_String;
Start : Positive := Expr'First;
Last : Positive := Start;
First_Tok : Character;
function Is_Higher_Precedence(Left, Right : Character) return Boolean is
Result : Boolean := False;
begin
case Left is
when '*' | '/' =>
case Right is
when '*' | '/' =>
Result := False;
when others =>
Result := True;
end case;
when '+' | '-' =>
case Right is
when '0'..'9' =>
Result := True;
when others =>
Result := False;
end case;
when others =>
Result := False;
end case;
return Result;
end Is_Higher_Precedence;
begin
while Last <= Expr'last loop
Get_Token(From => Expr, Starting => Start,
Token => Token, End_Index => Last);
Start := Last;
exit when Length(Token) = 0;
First_Tok := Element(Token,1);
if First_Tok in '0'..'9' then
Append(Postfix, ' ');
Append(Postfix, Token);
elsif First_Tok = '(' then
S.Push(Token);
elsif First_Tok = ')' then
while S.Depth > 0 and then Element(S.Top,1) /= '(' loop
S.Pop(Temp);
Append(Postfix, ' ');
Append(Postfix, Temp);
end loop;
S.Pop(Temp);
else
if S.Depth = 0 then
S.Push(Token);
else
while S.Depth > 0 and then Is_Higher_Precedence(Element(S.Top, 1), First_Tok) loop
S.Pop(Temp);
Append(Postfix, ' ');
Append(Postfix, Temp);
end loop;
S.Push(Token);
end if;
end if;
end loop;
while S.Depth > 0 loop
S.Pop(Temp);
Append(Postfix, Temp);
end loop;
return To_String(Postfix);
end To_Postfix;
function Evaluate_Postfix (Expr : String) return Integer is
function Image(Item : Integer) return String is
begin
return Integer'Image(Item);
end Image;
package Int_Stack is new Generic_Controlled_Stack(Integer, Image);
use Int_Stack;
S : Stack;
Start : Positive := Expr'First;
Last : Positive := Start;
Tok : Unbounded_String;
Right_Operand : Integer;
Left_Operand : Integer;
Result : Integer;
subtype Numeric is Character range '0'..'9';
begin
while Last <= Expr'Last loop
Get_Token(From => Expr, Starting => Start,
Token => Tok, End_Index => Last);
Start := Last;
exit when Length(Tok) = 0;
if Element(Tok,1) in Numeric then
S.Push(Integer'Value(To_String(Tok)));
else
S.Pop(Right_Operand);
S.Pop(Left_Operand);
case Element(Tok,1) is
when '*' =>
Result := Left_Operand * Right_Operand;
when '/' =>
Result := Left_Operand / Right_Operand;
when '+' =>
Result := Left_Operand + Right_Operand;
when '-' =>
Result := Left_Operand - Right_Operand;
when others =>
null;
end case;
S.Push(Result);
end if;
end loop;
S.Pop(Result);
return Result;
end Evaluate_Postfix;
begin
return Evaluate_Postfix(To_Postfix(Expr));
end Calculate;
begin
Put_line("(3 * 50) - (100 / 10)= " & Integer'Image(Calculate("(3 * 50) - (100 / 10)")));
end Arithmetic_Evaluator;
| |||