算法下午茶系列-初探虚拟机(1)[逆波兰表达式]

use feature "switch";
#构造运算符优先级数据
%priority_of_operation=(
'+'=>1,
'-'=>1,
'*'=>2,
'/'=>2,
'('=>0,
')'=>0
);
#待计算的表达式
$prepare_exec="5.98+((1+2211.12)*4)-3";
$prepare_endexpres=$prepare_exec;
#转化为逆波兰表达式
#建立运算符栈用于运算符的存储。
@operationstack=qw();
$exeexpress=$prepare_endexpres;
$result="";
print "待扫描的字符串为：$exeexpress\n";  
while (length($exeexpress)>0)
{
#顺序扫描表达式，如果当前字符是数字，则直接输出该数字
if ($exeexpress =~ /^(\d+)/ | $exeexpress =~/^((\d+)\.(\d*))/){
   print "数字为：$1\n";  	
   $result.=($1." ");   
   print "表达式为：$result\n";
   $exeexpress=substr($exeexpress,length($1),length($exeexpress)-length($1));
   print "待扫描的字符串为：$exeexpress\n";   
}
#若当前运算符为'('，直接入栈   
elsif($exeexpress =~ /^\(+?/){   
   print "操作符为：(\n";    
   print "运算符 ( 入栈\n";  
   push @operationstack,"(";  
   print "当前运算符栈：@operationstack\n";
   print "表达式为：$result\n";   
   $exeexpress=substr($exeexpress,1,length($exeexpress)-1);   
   print "待扫描的字符串为：$exeexpress\n";      
}   
#若为')'，出栈并顺序输出运算符直到遇到第一个'('，遇到的第一个'('出栈但不输出   
elsif($exeexpress =~ /^\)+?/){   
    print "操作符为：)\n";         
    $temp=pop @operationstack;
    while ($temp ne "(") {   
  	   $result.=($temp." ");   
	   print "运算符 $temp  出栈，表达式为：$result\n";
	   $temp=pop @operationstack;  
	   print "当前运算符栈：@operationstack\n"; 
    }         
    $exeexpress=substr($exeexpress,1,length($exeexpress)-1);       
    print "待扫描的字符串为：$exeexpress\n";        
} 
#若为四则运算符，比较栈顶元素与当前元素的优先级。如果 栈顶元素运算符优先级 >= 当前元素的优先级，出栈并顺序输出运算符直到 栈顶元素优先级 < 当前元素优先级，然后当前元素入栈； 
elsif($exeexpress =~/^(\+|\-|\*|\/)?(.*)$/)
{
	print "运算符为：$1\n"; 
	print "当前运算符栈：@operationstack\n"; 
    $curoperation=$1    ; 
	$topoperation=pop @operationstack;
	push @operationstack,$topoperation;		
	if ($topoperation){
		if ($priority_of_operation{$curoperation}>$priority_of_operation{$topoperation})
		{
		    #如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈
		    push @operationstack,$curoperation;		
			print "运算符 $curoperation  入栈\n";
            $exeexpress=substr($exeexpress,1,length($exeexpress)-1);	
            print "待扫描的字符串为：$exeexpress\n";  			
			
		}
		else{
#如果 栈顶元素运算符优先级 >= 当前元素的优先级，出栈并顺序输出运算符直到 栈顶元素优先级 < 当前元素优先级，然后当前元素入栈； 
			while ($priority_of_operation{$curoperation}<=$priority_of_operation{$topoperation})
			{
		        $topoperation=pop @operationstack;	
		        if (not $topoperation) {
		        	last;
		        }
                $result.=($topoperation." ");
		        print "运算符 $topoperation  出栈，表达式为：$result\n";
			}
			push @operationstack,$curoperation;
            $exeexpress=substr($exeexpress,1,length($exeexpress)-1);	
            print "待扫描的字符串为：$exeexpress\n";  			
		}
	}
	else{
			push @operationstack,$curoperation;
	        print "表达式为：$result\n"; 
            $exeexpress=substr($exeexpress,1,length($exeexpress)-1);	
            print "待扫描的字符串为：$exeexpress\n";  			
	}
	print "当前运算符栈：@operationstack\n";
}

}
while ((scalar @operationstack)>0){
	$result.=pop @operationstack;
}
print "表达式为：$result\n"; 
$mycode=$result;
@waitingexe=split (" ",$mycode);
$mylength= scalar  @waitingexe;
print "要计算的逆波兰式：$mycode\n";
print "开始逆波兰表达式计算\n";
@exestack=qw();
#输出当前栈的内容
print "当前栈的内容:@exestack\n";
for ($i=0;$i<$mylength;$i++){
#开始逆波兰式计算
 $myvar=$waitingexe[$i];
 print "读取到的元素为：$myvar   =>";
 given ($myvar){
    when ("+") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1+$num2;push @exestack,$result;print "$num1+$num2=$result，$num2和$num1出栈,$result入栈\n";}
	when ("-") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1-$num2;push @exestack,$result;print "$num1-$num2=$result，$num2和$num1出栈,$result入栈\n";}
	when ("*") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1*$num2;push @exestack,$result;print "$num1*$num2=$result，$num2和$num1出栈,$result入栈\n";}
	when ("/") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1/$num2;push @exestack,$result;print "$num1/$num2=$result，$num2和$num1出栈,$result入栈\n";}
	#数字直接入栈
	default    {push @exestack,$myvar;print "$myvar入栈\n";}
}
	#输出当前栈的内容
	print "当前栈的内容:@exestack=>";
}
$endresult=pop @exestack;
print "结果为：$endresult\n";

sub trim
{
        my $string = shift;
        $string =~ s/^\s+//;
        $string =~ s/\s+$//;
        return $string;
}

上述为求一个算法表达式的程序，执行结果及相关过程说明如下:

[deep@deep Documents]$ perl x.pl

待扫描的字符串为：5.98+((1+2211.12)*4)-3

数字为：5.98

表达式为：5.98 

待扫描的字符串为：+((1+2211.12)*4)-3

运算符为：+

当前运算符栈：

表达式为：5.98 

待扫描的字符串为：((1+2211.12)*4)-3

当前运算符栈： +

操作符为：(

运算符 ( 入栈

当前运算符栈： + (

表达式为：5.98 

待扫描的字符串为：(1+2211.12)*4)-3

操作符为：(

运算符 ( 入栈

当前运算符栈： + ( (

表达式为：5.98 

待扫描的字符串为：1+2211.12)*4)-3

数字为：1

表达式为：5.98 1 

待扫描的字符串为：+2211.12)*4)-3

运算符为：+

当前运算符栈： + ( (

运算符 +  入栈

待扫描的字符串为：2211.12)*4)-3

当前运算符栈： + ( ( +

数字为：2211.12

表达式为：5.98 1 2211.12 

待扫描的字符串为：)*4)-3

操作符为：)

运算符 +  出栈，表达式为：5.98 1 2211.12 + 

当前运算符栈： + (

待扫描的字符串为：*4)-3

运算符为：*

当前运算符栈： + (

运算符 *  入栈

待扫描的字符串为：4)-3

当前运算符栈： + ( *

数字为：4

表达式为：5.98 1 2211.12 + 4 

待扫描的字符串为：)-3

操作符为：)

运算符 *  出栈，表达式为：5.98 1 2211.12 + 4 * 

当前运算符栈： +

待扫描的字符串为：-3

运算符为：-

当前运算符栈： +

运算符 +  出栈，表达式为：5.98 1 2211.12 + 4 * + 

待扫描的字符串为：3

当前运算符栈：-

数字为：3

表达式为：5.98 1 2211.12 + 4 * + 3 

待扫描的字符串为：

表达式为：5.98 1 2211.12 + 4 * + 3 -

要计算的逆波兰式：5.98 1 2211.12 + 4 * + 3 -

开始逆波兰表达式计算

当前栈的内容:

读取到的元素为：5.98   =>5.98入栈

当前栈的内容:5.98=>读取到的元素为：1   =>1入栈

当前栈的内容:5.98 1=>读取到的元素为：2211.12   =>2211.12入栈

当前栈的内容:5.98 1 2211.12=>读取到的元素为：+   =>1+2211.12=2212.12，2211.12和1出栈,2212.12入栈

当前栈的内容:5.98 2212.12=>读取到的元素为：4   =>4入栈

当前栈的内容:5.98 2212.12 4=>读取到的元素为：*   =>2212.12*4=8848.48，4和2212.12出栈,8848.48入栈

当前栈的内容:5.98 8848.48=>读取到的元素为：+   =>5.98+8848.48=8854.46，8848.48和5.98出栈,8854.46入栈

当前栈的内容:8854.46=>读取到的元素为：3   =>3入栈

当前栈的内容:8854.46 3=>读取到的元素为：-   =>8854.46-3=8851.46，3和8854.46出栈,8851.46入栈

当前栈的内容:8851.46=>结果为：8851.46

[deep@deep Documents]$ 

下面是具体的讲解    

 

  逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。

一、 将正常表达式转换为逆波兰表达式的例子：

　　a+b   =>     a,b,+

　　a-(b+c) ---> a,b,c,+,-

　　a-(b+c)*d ---> a,b,c,+,d,*,-

　　a*(b+c)--->bc+a*

 

 

二、下面是逆波兰表达式求值 的讲解

 

1、伪代码

while有输入符号

• • 读入下一个符号
  • IF是一个操作数
    • 入栈
  • ELSE IF是一个操作符
    • 有一个先验的表格给出该操作符需要n个参数
    • IF堆栈中少于n个操作数
      • （错误） 用户没有输入足够的操作数
    • Else，n个操作数出栈
    • 计算操作符。
    • 将计算所得的值入栈
• IF栈内只有一个值
  • 这个值就是整个计算式的结果
• ELSE多于一个值
  • （错误） 用户输入了多余的操作数

 

 2、具体实现过程

中缀表达式“5 + ((1 + 2) * 4) − 3”写作

5 1 2 + 4 * + 3 −

下表给出了该逆波兰表达式从左至右求值的过程。

 

输入 操作 堆栈 注释

5	入栈	5
1	入栈	5, 1
2	入栈	5, 1, 2
+	加法运算	5, 3	(1, 2)出栈；将结果（3）入栈
4	入栈	5, 3, 4
*	乘法运算	5, 12	(3, 4)出栈；将结果（12）入栈
+	加法运算	17	(5, 12)出栈；将结果 (17)入栈
3	入栈	17, 3
−	减法运算	14	(17, 3)出栈；将结果（14）入栈

计算完成时，栈内只有一个操作数，这就是表达式的结果：14

 

 我们用PERL来实现逆波兰表达式的计算

use feature "switch";
$mycode="5 1 2 + 4 * + 3 -";
@waitingexe=split (" ",$mycode);
$mylength= scalar  @waitingexe;
print "要计算的逆波兰式：$mycode\n";
print "开始逆波兰表达式计算\n";
@exestack=qw();
#输出当前栈的内容
print "当前栈的内容:@exestack\n";
for ($i=0;$i<$mylength;$i++){
#开始逆波兰式计算
 $myvar=$waitingexe[$i];
 print "读取到的元素为：$myvar   =>";
 given ($myvar){
    when ("+") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1+$num2;push @exestack,$result;print "$num1+$num2=$result，$num2和$num1出栈,$result入栈\n";}
	when ("-") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1-$num2;push @exestack,$result;print "$num1-$num2=$result，$num2和$num1出栈,$result入栈\n";}
	when ("*") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1*$num2;push @exestack,$result;print "$num1*$num2=$result，$num2和$num1出栈,$result入栈\n";}
	when ("/") { $num2=pop @exestack;$num1=pop @exestack; $result=$num1/$num2;push @exestack,$result;print "$num1/$num2=$result，$num2和$num1出栈,$result入栈\n";}
	#数字直接入栈
	default    {push @exestack,$myvar;print "$myvar入栈\n";}
}
	#输出当前栈的内容
	print "当前栈的内容:@exestack=>";
}
$endresult=pop @exestack;
print "结果为：$endresult\n";

 

 

下面是运行结果

PS E:\temp> perl xx.pl
要计算的逆波兰式：5 1 2 + 4 * + 3 -
开始逆波兰表达式计算
当前栈的内容:
读取到的元素为：5   =>5入栈
当前栈的内容:5=>读取到的元素为：1   =>1入栈
当前栈的内容:5 1=>读取到的元素为：2   =>2入栈
当前栈的内容:5 1 2=>读取到的元素为：+   =>1+2=3，2和1出栈,3入栈
当前栈的内容:5 3=>读取到的元素为：4   =>4入栈
当前栈的内容:5 3 4=>读取到的元素为：*   =>3*4=12，4和3出栈,12入栈
当前栈的内容:5 12=>读取到的元素为：+   =>5+12=17，12和5出栈,17入栈
当前栈的内容:17=>读取到的元素为：3   =>3入栈
当前栈的内容:17 3=>读取到的元素为：-   =>17-3=14，3和17出栈,14入栈
当前栈的内容:14=>结果为：14
PS E:\temp>

 

三、将一个普通的中序表达式转换为逆波兰表达式的一般算法是：

　　(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

　　(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

　　(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

　　(4)如果不是数字，该字符则是运算符，此时需比较优先关系。

　　做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。

　　(5)重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

 

具体算法流程为:

下面是程序化算法流程：

　　1、建立运算符栈用于运算符的存储。

　　2、预处理表达式，正、负号前加0(如果一个加号（减号）出现在最前面或左括号后面，则该加号（减号）为正负号) 。

　　3、顺序扫描表达式，如果当前字符是数字（优先级为0的符号），则直接输出该数字；如果当前字符为运算符或括号（优先级不为0的符号），则判断第4点 。

　　4、若当前运算符为'('，直接入栈；

　　若为')'，出栈并顺序输出运算符直到遇到第一个'('，遇到的第一个'('出栈但不输出；

　　若为四则运算符，比较栈顶元素与当前元素的优先级：

　　如果 栈顶元素运算符优先级 >= 当前元素的优先级，出栈并顺序输出运算符直到 栈顶元素优先级 < 当前元素优先级，然后当前元素入栈；

　　如果 栈顶元素 < 当前元素，直接入栈。

　　5、重复第3点直到表达式扫描完毕。

　　6、顺序出栈并输出运算符直到栈元素为空。

 

use feature "switch";
#构造运算符优先级数据
%priority_of_operation=(
'+'=>1,
'-'=>1,
'*'=>2,
'/'=>2,
'('=>0,
')'=>0
);
#待计算的表达式
$prepare_exec="51*(32-18.32)+16";
$prepare_endexpres=$prepare_exec;
#转化为逆波兰表达式
#建立运算符栈用于运算符的存储。
@operationstack=qw();
$exeexpress=$prepare_endexpres;
$result="";
print "待扫描的字符串为：$exeexpress\n";  
while (length($exeexpress)>0)
{
#顺序扫描表达式，如果当前字符是数字，则直接输出该数字
if ($exeexpress =~ /^(\d+)/ | $exeexpress =~/^((\d+)\.(\d*))/){
   print "数字为：$1\n";  	
   $result.=($1." ");   
   print "表达式为：$result\n";
   $exeexpress=substr($exeexpress,length($1),length($exeexpress)-length($1));
   print "待扫描的字符串为：$exeexpress\n";   
}
#若当前运算符为'('，直接入栈   
elsif($exeexpress =~ /^\(+?/){   
   print "操作符为：(\n";    
   print "运算符 ( 入栈\n";  
   push @operationstack,"(";  
   print "当前运算符栈：@operationstack\n";
   print "表达式为：$result\n";   
   $exeexpress=substr($exeexpress,1,length($exeexpress)-1);   
   print "待扫描的字符串为：$exeexpress\n";      
}   
#若为')'，出栈并顺序输出运算符直到遇到第一个'('，遇到的第一个'('出栈但不输出   
elsif($exeexpress =~ /^\)+?/){   
    print "操作符为：)\n";         
    $temp=pop @operationstack;
    while ($temp ne "(") {   
  	   $result.=($temp." ");   
	   print "运算符 $temp  出栈，表达式为：$result\n";
	   $temp=pop @operationstack;  
	   print "当前运算符栈：@operationstack\n"; 
    }         
    $exeexpress=substr($exeexpress,1,length($exeexpress)-1);       
    print "待扫描的字符串为：$exeexpress\n";        
} 
#若为四则运算符，比较栈顶元素与当前元素的优先级。如果 栈顶元素运算符优先级 >= 当前元素的优先级，出栈并顺序输出运算符直到 栈顶元素优先级 < 当前元素优先级，然后当前元素入栈； 
elsif($exeexpress =~/^(\+|\-|\*|\/)?(.*)$/)
{
	print "运算符为：$1\n"; 
	print "当前运算符栈：@operationstack\n"; 
    $curoperation=$1    ; 
	$topoperation=pop @operationstack;
	push @operationstack,$topoperation;		
	if ($topoperation){
		if ($priority_of_operation{$curoperation}>$priority_of_operation{$topoperation})
		{
		    #如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈
		    push @operationstack,$curoperation;		
			print "运算符 $curoperation  入栈\n";
            $exeexpress=substr($exeexpress,1,length($exeexpress)-1);	
            print "待扫描的字符串为：$exeexpress\n";  			
			
		}
		else{
#如果 栈顶元素运算符优先级 >= 当前元素的优先级，出栈并顺序输出运算符直到 栈顶元素优先级 < 当前元素优先级，然后当前元素入栈； 
			while ($priority_of_operation{$curoperation}<=$priority_of_operation{$topoperation})
			{
		        $topoperation=pop @operationstack;	
		        if (not $topoperation) {
		        	last;
		        }
                $result.=($topoperation." ");
		        print "运算符 $topoperation  出栈，表达式为：$result\n";
			}
			push @operationstack,$curoperation;
            $exeexpress=substr($exeexpress,1,length($exeexpress)-1);	
            print "待扫描的字符串为：$exeexpress\n";  			
		}
	}
	else{
			push @operationstack,$curoperation;
	        print "表达式为：$result\n"; 
            $exeexpress=substr($exeexpress,1,length($exeexpress)-1);	
            print "待扫描的字符串为：$exeexpress\n";  			
	}
	print "当前运算符栈：@operationstack\n";
}

}
while ((scalar @operationstack)>0){
	$result.=pop @operationstack;
}
print "表达式为：$result\n"; 
sub trim
{
        my $string = shift;
        $string =~ s/^\s+//;
        $string =~ s/\s+$//;
        return $string;
}

 

 

输出结果如下：

 

 

[deep@deep Documents]$ perl x.pl

待扫描的字符串为：51*(32-18.32)+16

数字为：51

表达式为：51 

待扫描的字符串为：*(32-18.32)+16

运算符为：*

当前运算符栈：

表达式为：51 

待扫描的字符串为：(32-18.32)+16

当前运算符栈： *

操作符为：(

运算符 ( 入栈

当前运算符栈： * (

表达式为：51 

待扫描的字符串为：32-18.32)+16

数字为：32

表达式为：51 32 

待扫描的字符串为：-18.32)+16

运算符为：-

当前运算符栈： * (

运算符 -  入栈

待扫描的字符串为：18.32)+16

当前运算符栈： * ( -

数字为：18.32

表达式为：51 32 18.32 

待扫描的字符串为：)+16

操作符为：)

运算符 -  出栈，表达式为：51 32 18.32 - 

当前运算符栈： *

待扫描的字符串为：+16

运算符为：+

当前运算符栈： *

运算符 *  出栈，表达式为：51 32 18.32 - * 

待扫描的字符串为：16

当前运算符栈：+

数字为：16

表达式为：51 32 18.32 - * 16 

待扫描的字符串为：

表达式为：51 32 18.32 - * 16 +

[deep@deep Documents]$ 

 

 

转载请注意来源，有错误请指出

 

引用来源:

http://baike.baidu.com/view/552648.htm

http://zh.wikipedia.org/wiki/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E7%A4%BA%E6%B3%95