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}";
}
}