Parsing/Shunting-yard algorithm: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 43: | Line 43: | ||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="11l">F infix_to_postfix(infix) |
||
-V ops = ‘-+/*^’ |
-V ops = ‘-+/*^’ |
||
V sb = ‘’ |
V sb = ‘’ |
||
Line 85: | Line 85: | ||
V infix = ‘3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3’ |
V infix = ‘3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3’ |
||
print(‘infix: ’infix) |
print(‘infix: ’infix) |
||
print(‘postfix: ’infix_to_postfix(infix))</ |
print(‘postfix: ’infix_to_postfix(infix))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 94: | Line 94: | ||
=={{header|8th}}== |
=={{header|8th}}== |
||
< |
<syntaxhighlight lang="forth">\ Convert infix expression to postfix, using 'shunting-yard' algorithm |
||
\ https://en.wikipedia.org/wiki/Shunting-yard_algorithm |
\ https://en.wikipedia.org/wiki/Shunting-yard_algorithm |
||
Line 224: | Line 224: | ||
"Expected: \n" . "3 4 2 * 1 5 - 2 3 ^ ^ / +" . cr |
"Expected: \n" . "3 4 2 * 1 5 - 2 3 ^ ^ / +" . cr |
||
bye |
bye |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>NUMBER 3 |
<pre>NUMBER 3 |
||
Line 293: | Line 293: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN |
||
# parses s and returns an RPN expression using Dijkstra's "Shunting Yard" algorithm # |
# parses s and returns an RPN expression using Dijkstra's "Shunting Yard" algorithm # |
||
# s is expected to contain a valid infix expression containing single-digit numbers and single-character operators # |
# s is expected to contain a valid infix expression containing single-digit numbers and single-character operators # |
||
Line 370: | Line 370: | ||
print( ( "result: ", parse( "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" ), newline ) ) |
print( ( "result: ", parse( "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" ), newline ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 394: | Line 394: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{works with|AutoHotkey_L}} |
{{works with|AutoHotkey_L}} |
||
< |
<syntaxhighlight lang="ahk">SetBatchLines -1 |
||
#NoEnv |
#NoEnv |
||
Line 463: | Line 463: | ||
Space(n){ |
Space(n){ |
||
return n>0 ? A_Space Space(n-1) : "" |
return n>0 ? A_Space Space(n-1) : "" |
||
}</ |
}</syntaxhighlight> |
||
;Output |
;Output |
||
<pre style="height:30ex;overflow:scroll;">Testing string '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' |
<pre style="height:30ex;overflow:scroll;">Testing string '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' |
||
Line 493: | Line 493: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Requires a functioning ANSI terminal and Enter key. |
Requires a functioning ANSI terminal and Enter key. |
||
< |
<syntaxhighlight lang="c">#include <sys/types.h> |
||
#include <regex.h> |
#include <regex.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Line 677: | Line 677: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
;Output: |
;Output: |
||
Line 816: | Line 816: | ||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
{{works with|C sharp|7.0}} |
{{works with|C sharp|7.0}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 883: | Line 883: | ||
void Print(string action) => Console.WriteLine("{0,-4} {1,-18} {2}", action + ":", $"stack[ {string.Join(" ", stack.Reverse())} ]", $"out[ {string.Join(" ", output)} ]"); |
void Print(string action) => Console.WriteLine("{0,-4} {1,-18} {2}", action + ":", $"stack[ {string.Join(" ", stack.Reverse())} ]", $"out[ {string.Join(" ", output)} ]"); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 921: | Line 921: | ||
clang++ -Wall -pedantic-errors -O3 -std=c++17 a.cpp |
clang++ -Wall -pedantic-errors -O3 -std=c++17 a.cpp |
||
< |
<syntaxhighlight lang="cpp">#include <ciso646> |
||
#include <iostream> |
#include <iostream> |
||
#include <regex> |
#include <regex> |
||
Line 1,139: | Line 1,139: | ||
std::cerr << "error: " << e.what() << "\n"; |
std::cerr << "error: " << e.what() << "\n"; |
||
return 1; |
return 1; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>C:\Users\JRandom\cpp> a.exe 3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3 |
<pre>C:\Users\JRandom\cpp> a.exe 3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3 |
||
Line 1,176: | Line 1,176: | ||
Here is the code originally found under this C++ heading: |
Here is the code originally found under this C++ heading: |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <sstream> |
#include <sstream> |
||
#include <stack> |
#include <stack> |
||
Line 1,234: | Line 1,234: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
||
Line 1,240: | Line 1,240: | ||
=={{header|Ceylon}}== |
=={{header|Ceylon}}== |
||
< |
<syntaxhighlight lang="ceylon">import ceylon.collection { |
||
ArrayList |
ArrayList |
||
Line 1,345: | Line 1,345: | ||
assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +"); |
assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +"); |
||
print("\nthe result is ``rpn``"); |
print("\nthe result is ``rpn``"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>input is 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
<pre>input is 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
||
Line 1,376: | Line 1,376: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
Implemented as a state machine. The current state is the top of both the input queue and the operator stack. A signal function receives the current state and does a lookup to determine the signal to output. Based on the signal, the state (input queue and/or operator stack) is changed. The process iterates until both queue and stack are empty. |
Implemented as a state machine. The current state is the top of both the input queue and the operator stack. A signal function receives the current state and does a lookup to determine the signal to output. Based on the signal, the state (input queue and/or operator stack) is changed. The process iterates until both queue and stack are empty. |
||
< |
<syntaxhighlight lang="lisp">;;;; Parsing/infix to RPN conversion |
||
(defconstant operators "^*/+-") |
(defconstant operators "^*/+-") |
||
(defconstant precedence '(-4 3 3 2 2)) |
(defconstant precedence '(-4 3 3 2 2)) |
||
Line 1,465: | Line 1,465: | ||
(format t "~%INFIX:\"~A\"~%" expr) |
(format t "~%INFIX:\"~A\"~%" expr) |
||
(format t "RPN:\"~A\"~%" (rpn expr))))) |
(format t "RPN:\"~A\"~%" (rpn expr))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>CL-USER(2): (main) |
<pre>CL-USER(2): (main) |
||
Line 1,498: | Line 1,498: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="d">import std.container; |
||
import std.stdio; |
import std.stdio; |
||
Line 1,587: | Line 1,587: | ||
s.removeFront; |
s.removeFront; |
||
return v; |
return v; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,594: | Line 1,594: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(require 'hash) |
(require 'hash) |
||
(require 'tree) |
(require 'tree) |
||
Line 1,647: | Line 1,647: | ||
(writeln 'infix infix) |
(writeln 'infix infix) |
||
(writeln 'RPN (queue->list Q))) |
(writeln 'RPN (queue->list Q))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,673: | Line 1,673: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp">open System |
||
type action = Shift | ReduceStack | ReduceInput |
type action = Shift | ReduceStack | ReduceInput |
||
Line 1,767: | Line 1,767: | ||
shunting_yard (State((Array.toList input), [], [])) |
shunting_yard (State((Array.toList input), [], [])) |
||
|> (fun s -> s.report ReduceStack) |
|> (fun s -> s.report ReduceStack) |
||
0</ |
0</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> reduce [3] + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
<pre> reduce [3] + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
||
Line 1,808: | Line 1,808: | ||
===Source=== |
===Source=== |
||
< |
<syntaxhighlight lang="fortran"> MODULE COMPILER !At least of arithmetic expressions. |
||
INTEGER KBD,MSG !I/O units. |
INTEGER KBD,MSG !I/O units. |
||
Line 2,041: | Line 2,041: | ||
13 FORMAT (L6," RPN: >",A,"<") |
13 FORMAT (L6," RPN: >",A,"<") |
||
GO TO 10 |
GO TO 10 |
||
END</ |
END</syntaxhighlight> |
||
===Results=== |
===Results=== |
||
Line 2,101: | Line 2,101: | ||
===A fuller symbol table=== |
===A fuller symbol table=== |
||
The odd values for the precedences of the operators is driven by the model source being for a compiler able to handle much more complex arithmetic statements involving logical operations, variables, functions (some, like Max(a,b,c,...) with an arbitrary number of parameters), assignment within an expression, and conditionals such as <code>IF ''condition'' THEN ''exp1'' ELSE ''exp2'' OWISE ''exp3'' FI</code> - a three-value logic is employed. Similarly, ? stands for a "not a number" and ! for "Infinity". The fuller symbol table is... |
The odd values for the precedences of the operators is driven by the model source being for a compiler able to handle much more complex arithmetic statements involving logical operations, variables, functions (some, like Max(a,b,c,...) with an arbitrary number of parameters), assignment within an expression, and conditionals such as <code>IF ''condition'' THEN ''exp1'' ELSE ''exp2'' OWISE ''exp3'' FI</code> - a three-value logic is employed. Similarly, ? stands for a "not a number" and ! for "Infinity". The fuller symbol table is... |
||
< |
<syntaxhighlight lang="fortran">Caution! The apparent gaps in the sequence of precedence values in this table are *not* unused! |
||
Cunning ploys with precedence allow parameter evaluation, and right-to-left order as in x**y**z. |
Cunning ploys with precedence allow parameter evaluation, and right-to-left order as in x**y**z. |
||
INTEGER OPSYMBOLS !Recognised operator symbols. |
INTEGER OPSYMBOLS !Recognised operator symbols. |
||
Line 2,148: | Line 2,148: | ||
3 SYMB("^ ",14,2,"raise to power: also recognised is **."), !Uses the previous precedence level also! |
3 SYMB("^ ",14,2,"raise to power: also recognised is **."), !Uses the previous precedence level also! |
||
4 SYMB("**",14,2,"raise to power: also recognised is ^."), |
4 SYMB("**",14,2,"raise to power: also recognised is ^."), |
||
5 SYMB("! ",15,1,"factorial, sortof, just for fun.")/))</ |
5 SYMB("! ",15,1,"factorial, sortof, just for fun.")/))</syntaxhighlight> |
||
The USAGE field is for when there is a request for help, and the response uses the scanner's actual symbol table entries to formulate its assistance, rather than roll forth a separately-prepared wad of text. |
The USAGE field is for when there is a request for help, and the response uses the scanner's actual symbol table entries to formulate its assistance, rather than roll forth a separately-prepared wad of text. |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
No error checking. No extra credit output, but there are some comments in the code. |
No error checking. No extra credit output, but there are some comments in the code. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 2,224: | Line 2,224: | ||
} |
} |
||
return |
return |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,235: | Line 2,235: | ||
Simple with zero error handling; some extra credit. |
Simple with zero error handling; some extra credit. |
||
< |
<syntaxhighlight lang="haskell">import Text.Printf |
||
prec :: String -> Int |
prec :: String -> Int |
||
Line 2,293: | Line 2,293: | ||
z |
z |
||
) |
) |
||
$ simSYA $ words a</ |
$ simSYA $ words a</syntaxhighlight> |
||
Output: |
Output: |
||
Line 2,319: | Line 2,319: | ||
A more complete version with typed input, output and stack; StateT + Control.Lens for stateful actions; Either for both invalid tokens on parsing and unmatched parens when converting; readLine support. |
A more complete version with typed input, output and stack; StateT + Control.Lens for stateful actions; Either for both invalid tokens on parsing and unmatched parens when converting; readLine support. |
||
< |
<syntaxhighlight lang="haskell">{-# LANGUAGE LambdaCase #-} |
||
import Control.Applicative |
import Control.Applicative |
||
import Control.Lens |
import Control.Lens |
||
Line 2,415: | Line 2,415: | ||
Left msg -> putStrLn msg >> main |
Left msg -> putStrLn msg >> main |
||
Right ts -> putStrLn (showOutput (toRPN ts)) >> main |
Right ts -> putStrLn (showOutput (toRPN ts)) >> main |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre>Enter expression: 3 + ( ( 4 + 5 ) |
<pre>Enter expression: 3 + ( ( 4 + 5 ) |
||
Line 2,430: | Line 2,430: | ||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
< |
<syntaxhighlight lang="icon">procedure main() |
||
infix := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" |
infix := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" |
||
printf("Infix = %i\n",infix) |
printf("Infix = %i\n",infix) |
||
Line 2,493: | Line 2,493: | ||
every (s := "[ ") ||:= !L || " " |
every (s := "[ ") ||:= !L || " " |
||
return s || "]" |
return s || "]" |
||
end</ |
end</syntaxhighlight> |
||
{{libheader|Icon Programming Library}} |
{{libheader|Icon Programming Library}} |
||
Line 2,523: | Line 2,523: | ||
=={{header|J}}== |
=={{header|J}}== |
||
Code |
Code |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
NB. j does not have a verb based precedence. |
NB. j does not have a verb based precedence. |
||
NB. j evaluates verb noun sequences from right to left. |
NB. j evaluates verb noun sequences from right to left. |
||
Line 2,668: | Line 2,668: | ||
fulfill_requirement=: ;@:(' '&,&.>)@:algebra_to_rpn |
fulfill_requirement=: ;@:(' '&,&.>)@:algebra_to_rpn |
||
</syntaxhighlight> |
|||
</lang> |
|||
Demonstration |
Demonstration |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
fulfill_requirement '3+4*2/(1-5)^2^3' |
fulfill_requirement '3+4*2/(1-5)^2^3' |
||
3 4 2 * 1 5 - 2 3 ^ ^ / + |
3 4 2 * 1 5 - 2 3 ^ ^ / + |
||
Line 2,726: | Line 2,726: | ||
OUTPUT queue ^ ^ / + |
OUTPUT queue ^ ^ / + |
||
3 4 2 * 1 5 - 2 3 ^ ^ / + |
3 4 2 * 1 5 - 2 3 ^ ^ / + |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|7}} |
{{works with|Java|7}} |
||
< |
<syntaxhighlight lang="java">import java.util.Stack; |
||
public class ShuntingYard { |
public class ShuntingYard { |
||
Line 2,788: | Line 2,788: | ||
return sb.toString(); |
return sb.toString(); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 2,796: | Line 2,796: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
< |
<syntaxhighlight lang="javascript">function Stack() { |
||
this.dataStore = []; |
this.dataStore = []; |
||
this.top = 0; |
this.top = 0; |
||
Line 2,864: | Line 2,864: | ||
} |
} |
||
postfix += s.dataStore.reverse().join(" "); |
postfix += s.dataStore.reverse().join(" "); |
||
print(postfix);</ |
print(postfix);</syntaxhighlight> |
||
Output: |
Output: |
||
Line 2,873: | Line 2,873: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Translation from the Wikipedia reference article's pseudocode. |
Translation from the Wikipedia reference article's pseudocode. |
||
< |
<syntaxhighlight lang="julia"> |
||
function parseinfix2rpn(s) |
function parseinfix2rpn(s) |
||
outputq = [] |
outputq = [] |
||
Line 2,915: | Line 2,915: | ||
teststring = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" |
teststring = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" |
||
println("\nResult: $teststring becomes $(join(parseinfix2rpn(teststring), ' '))") |
println("\nResult: $teststring becomes $(join(parseinfix2rpn(teststring), ' '))") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 2,939: | Line 2,939: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">// version 1.2.0 |
||
import java.util.Stack |
import java.util.Stack |
||
Line 2,999: | Line 2,999: | ||
println("Postfix : ${infixToPostfix(e)}\n") |
println("Postfix : ${infixToPostfix(e)}\n") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,011: | Line 3,011: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
<syntaxhighlight lang="lb"> |
|||
<lang lb> |
|||
global stack$,queue$ |
global stack$,queue$ |
||
stack$="" |
stack$="" |
||
Line 3,127: | Line 3,127: | ||
wend |
wend |
||
end function |
end function |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,154: | Line 3,154: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
<syntaxhighlight lang="lua"> |
|||
<lang Lua> |
|||
-- Lua 5.3.5 |
-- Lua 5.3.5 |
||
-- Retrieved from: https://devforum.roblox.com/t/more-efficient-way-to-implement-shunting-yard/1328711 |
-- Retrieved from: https://devforum.roblox.com/t/more-efficient-way-to-implement-shunting-yard/1328711 |
||
Line 3,254: | Line 3,254: | ||
print('infix:', goodmath) |
print('infix:', goodmath) |
||
print('postfix:', shuntingYard(goodmath)) |
print('postfix:', shuntingYard(goodmath)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,308: | Line 3,308: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">rpn[str_] := |
||
StringRiffle[ |
StringRiffle[ |
||
ToString /@ |
ToString /@ |
||
Line 3,339: | Line 3,339: | ||
While[stack != {}, AppendTo[out, stack[[-1]]]; |
While[stack != {}, AppendTo[out, stack[[-1]]]; |
||
stack = stack[[;; -2]]]; out]]; |
stack = stack[[;; -2]]]; out]]; |
||
Print[rpn["3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]];</ |
Print[rpn["3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 4 2 * 1 5 - / 2 3 ^ ^ +</pre> |
<pre>3 4 2 * 1 5 - / 2 3 ^ ^ +</pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import tables, strutils, strformat |
||
type operator = tuple[prec:int, rassoc:bool] |
type operator = tuple[prec:int, rassoc:bool] |
||
Line 3,388: | Line 3,388: | ||
echo &"for infix expression: '{input}' \n", "\nTOKEN OP STACK RPN OUTPUT" |
echo &"for infix expression: '{input}' \n", "\nTOKEN OP STACK RPN OUTPUT" |
||
echo "postfix: ", shuntRPN(input.strip.split)</ |
echo "postfix: ", shuntRPN(input.strip.split)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,417: | Line 3,417: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
{{works with|ocaml|4.04}} |
{{works with|ocaml|4.04}} |
||
< |
<syntaxhighlight lang="ocaml"> |
||
type associativity = Left | Right;; |
type associativity = Left | Right;; |
||
Line 3,477: | Line 3,477: | ||
let postfix = shunting_yard tkns in |
let postfix = shunting_yard tkns in |
||
print_endline (intercalate " " postfix);; |
print_endline (intercalate " " postfix);; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">my %prec = ( |
||
'^' => 4, |
'^' => 4, |
||
'*' => 3, |
'*' => 3, |
||
Line 3,530: | Line 3,530: | ||
local $, = " "; |
local $, = " "; |
||
print shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'; |
print shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
||
Line 3,556: | Line 3,556: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{Trans|Go}} |
{{Trans|Go}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">bool</span> <span style="color: #000000;">show_workings</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
<span style="color: #004080;">bool</span> <span style="color: #000000;">show_workings</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
||
Line 3,639: | Line 3,639: | ||
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 * 2 + 1 - 5"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 2 * 1 + 5 -"</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 * 2 + 1 - 5"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 2 * 1 + 5 -"</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 * 2 / (1 - 5) ^ 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 2 * 1 5 - 2 ^ /"</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 * 2 / (1 - 5) ^ 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 2 * 1 5 - 2 ^ /"</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,694: | Line 3,694: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Note: "^" is a meta-character and must be escaped in strings |
Note: "^" is a meta-character and must be escaped in strings |
||
< |
<syntaxhighlight lang="picolisp">(de operator (Op) |
||
(member Op '("\^" "*" "/" "+" "-")) ) |
(member Op '("\^" "*" "/" "+" "-")) ) |
||
Line 3,734: | Line 3,734: | ||
(quit "Unbalanced Stack") ) |
(quit "Unbalanced Stack") ) |
||
(link (pop 'Stack)) |
(link (pop 'Stack)) |
||
(tab Fmt NIL (glue " " (made)) Stack) ) ) ) )</ |
(tab Fmt NIL (glue " " (made)) Stack) ) ) ) )</syntaxhighlight> |
||
Output: |
Output: |
||
< |
<syntaxhighlight lang="picolisp">: (shuntingYard "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3") |
||
Token Output Stack |
Token Output Stack |
||
3 3 |
3 3 |
||
Line 3,757: | Line 3,757: | ||
3 4 2 * 1 5 - 2 3 ^ ^ / + |
3 4 2 * 1 5 - 2 3 ^ ^ / + |
||
3 4 2 * 1 5 - 2 3 ^ ^ / + |
3 4 2 * 1 5 - 2 3 ^ ^ / + |
||
-> (3 4 2 "*" 1 5 "-" 2 3 "\^" "\^" "/" "+")</ |
-> (3 4 2 "*" 1 5 "-" 2 3 "\^" "\^" "/" "+")</syntaxhighlight> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
<syntaxhighlight lang="pl/i"> |
|||
<lang PL/I> |
|||
cvt: procedure options (main); /* 15 January 2012. */ |
cvt: procedure options (main); /* 15 January 2012. */ |
||
declare (in, stack, out) character (100) varying; |
declare (in, stack, out) character (100) varying; |
||
Line 3,843: | Line 3,843: | ||
end cvt; |
end cvt; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<lang> |
<syntaxhighlight lang="text"> |
||
INPUT STACK OUTPUT |
INPUT STACK OUTPUT |
||
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) ( |
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) ( |
||
Line 3,878: | Line 3,878: | ||
3 4 2 * 1 5 - 2 3 ^ ^ / + |
3 4 2 * 1 5 - 2 3 ^ ^ / + |
||
3 4 2 * 1 5 - 2 3 ^ ^ / + |
3 4 2 * 1 5 - 2 3 ^ ^ / + |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
Parenthesis are added to the operator table then special-cased in the code. |
Parenthesis are added to the operator table then special-cased in the code. |
||
This solution includes the extra credit. |
This solution includes the extra credit. |
||
< |
<syntaxhighlight lang="python">from collections import namedtuple |
||
from pprint import pprint as pp |
from pprint import pprint as pp |
||
Line 3,985: | Line 3,985: | ||
print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row))) |
print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row))) |
||
print('\n The final output RPN is: %r' % rp[-1][2])</ |
print('\n The final output RPN is: %r' % rp[-1][2])</syntaxhighlight> |
||
;Sample output: |
;Sample output: |
||
Line 4,017: | Line 4,017: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
;print column of width w |
;print column of width w |
||
Line 4,062: | Line 4,062: | ||
((if (lasso? x) <= <) (prec x) (prec y)))))]) |
((if (lasso? x) <= <) (prec x) (prec y)))))]) |
||
(shunt (append (reverse l) out) (cons x r) in (format "out ~a, push ~a" l x)))])]))) |
(shunt (append (reverse l) out) (cons x r) in (format "out ~a, push ~a" l x)))])]))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,087: | Line 4,087: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
<syntaxhighlight lang="raku" line> |
|||
<lang perl6> |
|||
my %prec = |
my %prec = |
||
'^' => 4, |
'^' => 4, |
||
Line 4,134: | Line 4,134: | ||
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'; |
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
||
Line 4,161: | Line 4,161: | ||
These REXX versions below allow multi-character tokens (both operands and operators). |
These REXX versions below allow multi-character tokens (both operands and operators). |
||
===assume expression is correct=== |
===assume expression is correct=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/ |
||
parse arg x /*obtain optional argument from the CL.*/ |
parse arg x /*obtain optional argument from the CL.*/ |
||
if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ |
if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ |
||
Line 4,212: | Line 4,212: | ||
/*──────────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────────*/ |
||
isOp: return pos(arg(1),rOp) \== 0 /*is the first argument a "real" operator? */ |
isOp: return pos(arg(1),rOp) \== 0 /*is the first argument a "real" operator? */ |
||
show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</ |
show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</syntaxhighlight> |
||
'''output''' when using the default input: |
'''output''' when using the default input: |
||
<pre> |
<pre> |
||
Line 4,252: | Line 4,252: | ||
The '''select''' group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source. |
The '''select''' group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source. |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/ |
||
parse arg x /*obtain optional argument from the CL.*/ |
parse arg x /*obtain optional argument from the CL.*/ |
||
if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ |
if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ |
||
Line 4,308: | Line 4,308: | ||
/*──────────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────────*/ |
||
isOp: return pos(arg(1), Rop) \== 0 /*is the first argument a "real" operator? */ |
isOp: return pos(arg(1), Rop) \== 0 /*is the first argument a "real" operator? */ |
||
show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</ |
show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</syntaxhighlight> |
||
'''output''' when using the input: <tt> ) ( </tt> |
'''output''' when using the input: <tt> ) ( </tt> |
||
<pre> |
<pre> |
||
Line 4,318: | Line 4,318: | ||
See [[Parsing/RPN/Ruby]] |
See [[Parsing/RPN/Ruby]] |
||
< |
<syntaxhighlight lang="ruby">rpn = RPNExpression.from_infix("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")</syntaxhighlight> |
||
outputs |
outputs |
||
<pre>for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
<pre>for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
||
Line 4,342: | Line 4,342: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">type Number = f64; |
||
#[derive(Debug, Copy, Clone, PartialEq)] |
#[derive(Debug, Copy, Clone, PartialEq)] |
||
Line 4,501: | Line 4,501: | ||
calculate(postfix_tokens) |
calculate(postfix_tokens) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">var prec = Hash( |
||
'^' => 4, |
'^' => 4, |
||
'*' => 3, |
'*' => 3, |
||
Line 4,562: | Line 4,562: | ||
} |
} |
||
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ')</ |
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,589: | Line 4,589: | ||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
< |
<syntaxhighlight lang="sml">structure Operator = struct |
||
datatype associativity = LEFT | RIGHT |
datatype associativity = LEFT | RIGHT |
||
type operator = { symbol : char, assoc : associativity, precedence : int } |
type operator = { symbol : char, assoc : associativity, precedence : int } |
||
Line 4,698: | Line 4,698: | ||
parse' tokens [] [] |
parse' tokens [] [] |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">import Foundation |
||
// Using arrays for both stack and queue |
// Using arrays for both stack and queue |
||
Line 4,876: | Line 4,876: | ||
print("input: \(input)") |
print("input: \(input)") |
||
print("output: \(output)") |
print("output: \(output)") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,884: | Line 4,884: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
# Helpers |
# Helpers |
||
Line 4,941: | Line 4,941: | ||
} |
} |
||
puts [shunting "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]</ |
puts [shunting "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 4,998: | Line 4,998: | ||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
||
< |
<syntaxhighlight lang="bash">#!/bin/sh |
||
getopprec() { |
getopprec() { |
||
Line 5,100: | Line 5,100: | ||
} |
} |
||
infix 3 + 4 \* 2 / \( 1 - 5 \) ^ 2 ^ 3</ |
infix 3 + 4 \* 2 / \( 1 - 5 \) ^ 2 ^ 3</syntaxhighlight> |
||
===Output=== |
===Output=== |
||
<lang>Token: 3 |
<syntaxhighlight lang="text">Token: 3 |
||
Output: 3 |
Output: 3 |
||
Operators: |
Operators: |
||
Line 5,150: | Line 5,150: | ||
End parsing |
End parsing |
||
Output: 3 4 2 1 5 - 2 3 ^ ^ / * + |
Output: 3 4 2 1 5 - 2 3 ^ ^ / * + |
||
Operators:</ |
Operators:</syntaxhighlight> |
||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
Line 5,156: | Line 5,156: | ||
{{trans|Liberty BASIC}} |
{{trans|Liberty BASIC}} |
||
< |
<syntaxhighlight lang="vba">Option Explicit |
||
Option Base 1 |
Option Base 1 |
||
Line 5,265: | Line 5,265: | ||
Function Peek(stack) |
Function Peek(stack) |
||
Peek = stack(UBound(stack)) |
Peek = stack(UBound(stack)) |
||
End Function</ |
End Function</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,290: | Line 5,290: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Module Module1 |
||
Class SymbolType |
Class SymbolType |
||
Public ReadOnly symbol As String |
Public ReadOnly symbol As String |
||
Line 5,372: | Line 5,372: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3: stack[ ] out[ 3 ] |
<pre>3: stack[ ] out[ 3 ] |
||
Line 5,396: | Line 5,396: | ||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
{{libheader|Wren-pattern}} |
{{libheader|Wren-pattern}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/seq" for Stack |
||
import "/pattern" for Pattern |
import "/pattern" for Pattern |
||
Line 5,447: | Line 5,447: | ||
System.print("Infix : %(e)") |
System.print("Infix : %(e)") |
||
System.print("Postfix : %(infixToPostfix.call(e))\n") |
System.print("Postfix : %(infixToPostfix.call(e))\n") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,462: | Line 5,462: | ||
{{trans|VBA}} |
{{trans|VBA}} |
||
<syntaxhighlight lang="xojo"> |
|||
<lang Xojo> |
|||
Function ShuntingYard(strInfix As String) As String |
Function ShuntingYard(strInfix As String) As String |
||
Line 5,633: | Line 5,633: | ||
End Function</ |
End Function</syntaxhighlight> |
||
Line 5,661: | Line 5,661: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="zkl">var input="3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"; |
||
var opa=Dictionary("^",T(4,True), "*",T(3,False), // op:(prec,rAssoc) |
var opa=Dictionary("^",T(4,True), "*",T(3,False), // op:(prec,rAssoc) |
||
Line 5,711: | Line 5,711: | ||
"Queue|".println(rpn); |
"Queue|".println(rpn); |
||
println(); |
println(); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:20ex;overflow:scroll;"> |
<pre style="height:20ex;overflow:scroll;"> |