use feature "switch";
# Construct operator priority data
%priority_of_operation=(
'+'=>1,
'-'=>1,
'*'=>2,
'/'=>2,
'('=>0,
')'=>0
);
# Expression to be calculated
$prepare_exec="5.98+((1+2211.12)*4)-3";
$prepare_endexpres=$prepare_exec;
# Convert to Reverse Polish Notation
# Create operator stack for storing operators
@operationstack=qw();
$exeexpress=$prepare_endexpres;
$result="";
print "String to scan: $exeexpress\n";
while (length($exeexpress)>0)
{
# Scan expression sequentially, if current character is a number, output it directly
if ($exeexpress =~ /^(\d+)/ | $exeexpress =~/^((\d+)\.(\d*))/){
print "Number: $1\n";
$result.=($1." ");
print "Expression: $result\n";
$exeexpress=substr($exeexpress,length($1),length($exeexpress)-length($1));
print "String to scan: $exeexpress\n";
}
# If current operator is '(', push directly to stack
elsif($exeexpress =~ /^\(+?/){
print "Operator: (\n";
print "Operator ( pushed to stack\n";
push @operationstack,"(";
print "Current operator stack: @operationstack\n";
print "Expression: $result\n";
$exeexpress=substr($exeexpress,1,length($exeexpress)-1);
print "String to scan: $exeexpress\n";
}
# If it's ')', pop and output operators sequentially until encountering first '(', first '(' is popped but not output
elsif($exeexpress =~ /^\)+?/){
print "Operator: )\n";
$temp=pop @operationstack;
while ($temp ne "(") {
$result.=($temp." ");
print "Operator $temp popped, expression: $result\n";
$temp=pop @operationstack;
print "Current operator stack: @operationstack\n";
}
$exeexpress=substr($exeexpress,1,length($exeexpress)-1);
print "String to scan: $exeexpress\n";
}
# If it's arithmetic operator, compare priority of top stack element with current element. If priority of top stack element operator >= priority of current element, pop and output operators sequentially until priority of top stack element < priority of current element, then push current element to stack;
elsif($exeexpress =~/^(\+|\-|\*|\/)?(.*)$/)
{
print "Operator: $1\n";
print "Current operator stack: @operationstack\n";
$curoperation=$1 ;
$topoperation=pop @operationstack;
push @operationstack,$topoperation;
if ($topoperation){
if ($priority_of_operation{$curoperation}>$priority_of_operation{$topoperation})
{
# If this character's priority is higher than the operator at top of operator stack, push this operator to stack
push @operationstack,$curoperation;
print "Operator $curoperation pushed to stack\n";
$exeexpress=substr($exeexpress,1,length($exeexpress)-1);
print "String to scan: $exeexpress\n";
}
else{
# If priority of top stack element operator >= priority of current element, pop and output operators sequentially until priority of top stack element < priority of current element, then push current element to stack;
while ($priority_of_operation{$curoperation}<=$priority_of_operation{$topoperation})
{
$topoperation=pop @operationstack;
if (not $topoperation) {
last;
}
$result.=($topoperation." ");
print "Operator $topoperation popped, expression: $result\n";
}
push @operationstack,$curoperation;
$exeexpress=substr($exeexpress,1,length($exeexpress)-1);
print "String to scan: $exeexpress\n";
}
}
else{
push @operationstack,$curoperation;
print "Expression: $result\n";
$exeexpress=substr($exeexpress,1,length($exeexpress)-1);
print "String to scan: $exeexpress\n";
}
print "Current operator stack: @operationstack\n";
}
}
while ((scalar @operationstack)>0){
$result.=pop @operationstack;
}
print "Expression: $result\n";
$mycode=$result;
@waitingexe=split (" ",$mycode);
$mylength= scalar @waitingexe;
print "Reverse Polish Notation to calculate: $mycode\n";
print "Starting Reverse Polish Notation calculation\n";
@exestack=qw();
# Output current stack contents
print "Current stack contents: @exestack\n";
for ($i=0;$i<$mylength;$i++){
# Start Reverse Polish Notation calculation
$myvar=$waitingexe[$i];
print "Element read: $myvar =>";
given ($myvar){
when ("+") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1+$num2;push @exestack,$result;print "$num1+$num2=$result, $num2 and $num1 popped, $result pushed\n";}
when ("-") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1-$num2;push @exestack,$result;print "$num1-$num2=$result, $num2 and $num1 popped, $result pushed\n";}
when ("*") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1*$num2;push @exestack,$result;print "$num1*$num2=$result, $num2 and $num1 popped, $result pushed\n";}
when ("/") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1/$num2;push @exestack,$result;print "$num1/$num2=$result, $num2 and $num1 popped, $result pushed\n";}
# Numbers pushed directly to stack
default {push @exestack,$myvar;print "$myvar pushed to stack\n";}
}
# Output current stack contents
print "Current stack contents: @exestack=>";
}
$endresult=pop @exestack;
print "Result: $endresult\n";
sub trim
{
my $string = shift;
$string =~ s/^\s+//;
$string =~ s/\s+$//;
return $string;
}
The above code evaluates a mathematical expression.
We will use the following example to illustrate the computation process.
The infix expression "5 + ((1 + 2) * 4) - 3" is written in Reverse Polish Notation as:
5 1 2 + 4 * + 3 -
The table below illustrates the step-by-step evaluation of this RPN expression from left to right.
| Input | Action | Stack | Comment |
|---|---|---|---|
| 5 | Push | 5 | |
| 1 | Push | 5, 1 | |
| 2 | Push | 5, 1, 2 | |
| + | Addition | 5, 3 | Pop (1, 2); push result (3) |
| 4 | Push | 5, 3, 4 | |
| * | Multiplication | 5, 12 | Pop (3, 4); push result (12) |
| + | Addition | 17 | Pop (5, 12); push result (17) |
| 3 | Push | 17, 3 | |
| - | Subtraction | 14 | Pop (17, 3); push result (14) |
When the calculation is complete, only one operand remains in the stack, which is the final result of the expression: 14.
Top comments (0)