expr := number | expr ws unary_operator | expr ws expr ws binary_operator number := digit {digit} [ '.' {digit} ] | '.' digit {digit} digit := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' unary_op := "chs" | "abs" | "sqr" | "sqrt" | "sin" | "cos" | "tan" binary_op := '+' | '-' | '*' | '/' | '^' ws := ' ' | '\t' | '\r' | '\n' Note: I use "chs" as shorthand for 'c' 'h' 's' #### digit -> /(? \d )/msx number -> /(? (?&digit)+ (?:[.](?&digit)*) | [.](?&digit)+ )/msx #### qr{ (?(DEFINE) (? (?&number) | (?&expr) \s+ (&unary_op) | (?&expr) \s+ (?&expr) \s+ (&binary_op) ) (? \d+ (?: [.] \d* )? | [.] \d+ ) (? (?: chs | abs | sqr | sqrt | sin | cos | tan ) ) (? [-+/*^] ) ) \A \s* (?&expr) \s* \z }msx; #### String found where operator expected at (re_eval 10) line 1, near "say "matching at "" (Do you need to predeclare say?) syntax error at (re_eval 10) line 1, near "say "matching at "" Compilation failed in regexp at rpg.pl line 137. #### (?(DEFINE) (? (?&number) (?: \s* (?: (?&number) | (?&unary_op) | (?&binary_op) ) )* ) (? (?> \d+ (?: [.] \d* )? | [.] \d+ ) (?{ $^R + 1}) ) (? (?i: chs | abs | sqr | sqrt | sin | cos | tan ) (?![a-zA-Z]) ) (? [-+/*^] (?{ $^R - 1 }) ) ) \A \s* (?&expr) \s* \z (?(?{ $^R != 1 }) (*FAIL) ) }msx #### /(?(?&NAME_PAT))(?(?&ADDRESS_PAT)) (?(DEFINE) (?....) (?....) )/x #### (? ( (?> \d+ (?: [.] \d* )? | [.] \d+ ) ) (?{ local @stack = ( @stack, $^N ) }) ) #### qr{ (?(DEFINE) (? (?&number) (?: \s+ (?: (?&number) | (?&unary_op) | (?&binary_op) ) )* ) (? ( \d+ (?: [.] \d* )? | [.] \d+ ) (?{ local @stack = ( @stack, $^N ) }) ) (? ( chs | abs | sqr | sqrt | sin | cos | tan ) (?(?{ @stack < 1 }) (*FAIL) ) (?{ local @stack = @stack; $operators{$^N}->($stack[-1]) }) ) (? ( [-+/*^] ) (?(?{ @stack < 2 }) (*FAIL) ) (?{ local @stack = @stack; $operators{$^N}->($stack[-2], pop @stack) }) ) ) \A \s* (?&expr) \s* \z (?(?{ @stack != 1 }) (*FAIL) ) (?{ $result = $stack[0] }) | (?{ $result = undef }) (*FAIL) }msx #### qr{ (?{ @stack = (); $result = undef; }) \A \s* (? \d+ (?: [.] \d* )? | [.] \d+ ) (?{ push @stack, $+{start_number} }) (?> \s+ (?: (? \d+ (?: [.] \d* )? | [.] \d+ ) (?{ push @stack, $+{number} }) | (? chs | abs | sqrt | sqr | sin | cos | tan ) (?(?{ @stack < 1 }) (*FAIL) ) (?{ $operators{ $+{unary_op} }->($stack[-1]) }) | (? [-+/*^] ) (?(?{ @stack < 2 }) (*FAIL) ) (?{ $operators{ $+{binary_op} }->($stack[-2], pop @stack) }) ) )* \s* \z (?(?{ @stack != 1 }) (*FAIL) ) (?{ $result = $stack[0] }) }msx, #### my $input = join ' ', (1) x 1_001, ('+') x 1_000; cmpthese( 100, { recursive => sub { $input1 =~ $RPN1 }, iterative => sub { $input2 =~ $RPN2 }, }, ); s/iter recursive flat recursive 1.35 -- -99% iterative 1.47e-02 9103% -- #### # my $input = join ' ', 1, ('1 +') x 1_000; Rate recursive iterative recursive 40.5/s -- -40% iterative 67.6/s 67% -- #### # my $input = join ' ', (1) x 4, ('+') x 3; Rate recursive iterative recursive 14306/s -- -17% iterative 17271/s 21% -- #### qr{ \A \s* (? \d+ (?: [.] \d* )? | [.] \d+ ) (?{ 1 }) (?> \s+ (?: (? \d+ (?: [.] \d* )? | [.] \d+ ) (?{ $^R + 1}) | (? chs | abs | sqrt | sqr | sin | cos | tan ) | (? [-+/*^] ) (?{ $^R - 1 }) ) )* \s* \z (?(?{ $^R != 1 }) (*FAIL) ) }msx, #### # my $input = join ' ', (1) x 1_001, ('+') x 1_000; Rate recursive iterative recursive 83.6/s -- -80% iterative 415/s 396% -- # my $input = join ' ', 1, ('1 +') x 1_000; Rate recursive iterative recursive 82.2/s -- -78% iterative 376/s 357% -- # my $input = join ' ', (1) x 4, ('+') x 3; Rate recursive iterative recursive 28249/s -- -69% iterative 92593/s 228% -- #### #!//net/perl/5.10.0/bin/perl use warnings; use strict; use 5.010_000; our @stack; our $result; my %operators = ( '+' => sub { $_[0] += $_[1] }, '-' => sub { $_[0] -= $_[1] }, '/' => sub { $_[0] /= $_[1] }, '*' => sub { $_[0] *= $_[1] }, '^' => sub { $_[0]**= $_[1] }, chs => sub { $_[0] = -$_[0] }, abs => sub { $_[0] = abs $_[0] }, sqr => sub { $_[0] *= $_[0] }, sqrt => sub { $_[0] = sqrt $_[0] }, sin => sub { $_[0] = sin $_[0] }, cos => sub { $_[0] = cos $_[0] }, tan => sub { $_[0] = sin $_[0] / cos $_[0] }, ); my $RPN = qr{ (?{ @stack = () }) (?{ $result = undef }) \A \s* (? \d+ (?: [.] \d* )? | [.] \d+ ) (?{ push @stack, $+{start_number} }) (?> \s+ (?: (? \d+ (?: [.] \d* )? | [.] \d+ ) (?{ push @stack, $+{number} }) | (? chs | abs | sqrt | sqr | sin | cos | tan ) (?(?{ @stack < 1 }) (*FAIL) ) (?{ $operators{ $+{unary_op} }->($stack[-1]) }) | (? [-+/*^] ) (?(?{ @stack < 2 }) (*FAIL) ) (?{ $operators{ $+{binary_op} }->($stack[-2], pop @stack) }) ) )* \s* \z (?(?{ @stack != 1 }) (*FAIL) ) (?{ $result = $stack[0] }) }msx, my %input = ( 'fail' => undef, '1 fail' => undef, '123' => 123, '123.456' => 123.456, '123.456 +' => undef, '.456' => .456, '123.' => 123., '123 /' => undef, ' 123 ' => 123, '123 chs' => -123, '123 chs chs' => 123, '123 chs chs chs' => -123, '123 chs chs chs chs' => 123, '4 2 ^' => 16, '4 2 /' => 2, '4 2 +' => 6, '4 2 *' => 8, '4 2 -' => 2, '12 34+' => undef, '12 34' => undef, '12 34 + +' => undef, '12 34 56 + +' => 102, '12 34 + 56 +' => 102, '123 chs 34 *' => -4_182, '123 34 * chs' => -4_182, '24' => 24, '24 abs' => 24, '24abs' => undef, '24abssqrt' => undef, '1 24abs+sqrt' => undef, '1 24 abs + sqrt' => 5, '24 chs abs' => 24, '24 chs' => -24, '25 abs sqrt' => 5, '25 chs abs sqrt' => 5, '24 4 + chs sqr' => 784, '34 2 / 2 ^' => 289, '3 34 2 / 2 ^ *' => 867, ); foreach my $line ( keys %input ) { my ($expression) = $line =~ /($RPN)/; if ( !defined $result && !defined $input{$line} ) { say "OK: $line is invalid, got no result"; } elsif ( !defined $result ) { say "FAILED: $line expected $input{$line}, got no result"; } elsif ( !defined $input{$line} ) { say "FAILED: $line got $result, expected no result"; } elsif ( $result == $input{$line} ) { say "OK: $expression = $result"; } else { say "FAILED: $line got $result, expected $input{$line}"; } }