逆波兰式与递归计算代码,Perl代码库,德仔网

代码语言
代码分类
【Perl】逆波兰式与递归计算
作者:dezai / 发布于2014/9/12/ 593

	#!/usr/bin/perl
	use strict;
	use warnings;
	use Data::Dumper;
	while(1){
	 my $data=&get_input();
	 if(!$data){
	 print "your expr is illegal,please check it\n";next;
	 }
	 my @tree=&get_tree($data);
	 print "The tree is: \n", Dumper(@tree)," \n";
	 my $result=&count($tree[0]);
	 print "The result of the expr is: $result\n";
	}
	######获得输入数据函数
	sub get_input{
	 print "Input your expr>>";
	 chomp( my $inputdata=<STDIN>);
	 $inputdata=~s/\s//g; #去除所有的空白符
	 if(!$inputdata){exit;}
	 if($inputdata=~/[a-zA-Z\.]/) { #做简单检查是否存在小数或者字符出现
	 return 0;}
	 $inputdata=join("",$inputdata,"#") if (substr($inputdata,length($inputdata)-1,1) ne "#"); #在最后补#
	}
	#get the tree of the expr
	sub get_tree{
	 my $data=pop;
	 my ($stop,$top,$ch,@stack,@tree);
	 $top=0;$stack[0]='#';
	 while($top<length($data)){
	 $ch=substr($data,$top,1);
	 if($ch eq "+" or $ch eq "-"){
	 my $op=pop(@stack);
	 if($op eq '#' or $op eq '(' or $op eq '[' or $op eq '{'){
	 push(@stack,$op);push(@stack,$ch);}
	 else{
	 push(@stack,$op);
	 while(1){
	 my $op=pop(@stack);
	 if($op eq '#' or $op eq '(' or $op eq '[' or $op eq '{'){
	 push(@stack,$op);push(@stack,$ch); last;}
	 else{
	 my @node;
	 push(@node,$op);push(@node,pop(@tree));
	 push(@node,pop(@tree));push(@tree,[@node]);
	 }
	 }
	 }
	 $top=$top+1; next;
	 }
	 if($ch eq "*" or $ch eq "/")
	 {
	 my $op=pop(@stack);
	 if($op ne "*" and $op ne "/"){
	 push(@stack,$op);push(@stack,$ch);}
	 else{
	 push(@stack,$op);
	 while(1){
	 my $op=pop(@stack);
	 if($op ne "*" and $op ne "/"){
	 push(@stack,$op);push(@stack,$ch);last;}
	 else {
	 my @node;
	 push(@node,$op);push(@node,pop(@tree));
	 push(@node,pop(@tree));push(@tree,[@node]);
	 }
	 }
	 }
	 $top=$top+1;next;
	 }
	 if($ch eq '(' or $ch eq '{' or $ch eq '['){
	 push(@stack,$ch);$top=$top+1;next;
	 }
	 if($ch eq ')' or $ch eq ']' or $ch eq '}'){
	 while(1){
	 my $op=pop(@stack);
	 if($op eq '(' or $op eq '[' or $op eq '{'){
	 last;}
	 my @node;
	 push(@node,$op); push(@node,pop(@tree));
	 push(@node,pop(@tree)); push(@tree,[@node])
	 }
	 $top=$top+1;next;
	 }
	 if($ch eq '#'){
	 while(1){
	 my $op=pop(@stack);
	 if($op eq '#'){
	 last;}
	 else{
	 my @node;
	 push(@node,$op);push(@node,pop(@tree));
	 push(@node,pop(@tree));push(@tree,[@node]);
	 }
	 }
	 $top=$top+1;next;
	 }
	 if($ch ge '0' and $ch le '9'){
	 my $num=0;
	 while($ch ge '0' and $ch le '9'){
	 $num=$num*10+$ch; $top=$top+1;
	 $ch=substr($data,$top,1);
	 }
	 push(@tree,$num); next;
	 }
	 else{
	 $top=$top+1;
	 }
	 }
	 return reverse @tree;
	}
	
	#####检查是否为引用
	sub judge_digit
	{
	 my $data=shift;
	 if(ref($data) eq "ARRAY"){
	 return 0;}
	 else{
	 return 1;}
	}
	#####根据树计算最终结果
	########利用递归函数实现
	sub count
	{
	 my $x=shift;
	 my @data=@{$x};
	 if(judge_digit($data[1])==0){
	 $data[1]=count($data[1]);
	 }
	 if(judge_digit($data[2])==0){
	 $data[2]=count($data[2]);
	 }
	 if($data[0] eq "+"){
	 return $data[1]+$data[2];
	 }elsif($data[0] eq "-") {
	 return $data[2]-$data[1];
	 }elsif($data[0] eq "*"){
	 return $data[1]*$data[2];
	 }elsif($data[0] eq "/") {
	 return $data[2]/$data[1];
	 }
	}
试试其它关键字
　逆波兰式　　递归计算　
同语言下
可能有用的
dezai贡献的其它代码(1065)