Parsing/Shunting-yard algorithm: Difference between revisions

m
syntax highlighting fixup automation
m (syntax highlighting fixup automation)
Line 43:
{{trans|Java}}
 
<langsyntaxhighlight lang="11l">F infix_to_postfix(infix)
-V ops = ‘-+/*^’
V sb = ‘’
Line 85:
V infix = ‘3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3’
print(‘infix: ’infix)
print(‘postfix: ’infix_to_postfix(infix))</langsyntaxhighlight>
 
{{out}}
Line 94:
 
=={{header|8th}}==
<langsyntaxhighlight lang="forth">\ Convert infix expression to postfix, using 'shunting-yard' algorithm
\ https://en.wikipedia.org/wiki/Shunting-yard_algorithm
 
Line 224:
"Expected: \n" . "3 4 2 * 1 5 - 2 3 ^ ^ / +" . cr
bye
</syntaxhighlight>
</lang>
{{out}}
<pre>NUMBER 3
Line 293:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<langsyntaxhighlight lang="algol68">BEGIN
# 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 #
Line 370:
 
print( ( "result: ", parse( "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" ), newline ) )
END</langsyntaxhighlight>
{{out}}
<pre>
Line 394:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<langsyntaxhighlight AHKlang="ahk">SetBatchLines -1
#NoEnv
 
Line 463:
Space(n){
return n>0 ? A_Space Space(n-1) : ""
}</langsyntaxhighlight>
;Output
<pre style="height:30ex;overflow:scroll;">Testing string '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
Line 493:
=={{header|C}}==
Requires a functioning ANSI terminal and Enter key.
<langsyntaxhighlight lang="c">#include <sys/types.h>
#include <regex.h>
#include <stdio.h>
Line 677:
 
return 0;
}</langsyntaxhighlight>
 
;Output:
Line 816:
=={{header|C sharp}}==
{{works with|C sharp|7.0}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 883:
void Print(string action) => Console.WriteLine("{0,-4} {1,-18} {2}", action + ":", $"stack[ {string.Join(" ", stack.Reverse())} ]", $"out[ {string.Join(" ", output)} ]");
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 921:
clang++ -Wall -pedantic-errors -O3 -std=c++17 a.cpp
 
<langsyntaxhighlight lang="cpp">#include <ciso646>
#include <iostream>
#include <regex>
Line 1,139:
std::cerr << "error: " << e.what() << "\n";
return 1;
}</langsyntaxhighlight>
{{out}}
<pre>C:\Users\JRandom\cpp> a.exe 3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3
Line 1,176:
Here is the code originally found under this C++ heading:
{{trans|Java}}
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <sstream>
#include <stack>
Line 1,234:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 1,240:
 
=={{header|Ceylon}}==
<langsyntaxhighlight lang="ceylon">import ceylon.collection {
 
ArrayList
Line 1,345:
assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +");
print("\nthe result is ``rpn``");
}</langsyntaxhighlight>
{{out}}
<pre>input is 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 1,376:
=={{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.
<langsyntaxhighlight lang="lisp">;;;; Parsing/infix to RPN conversion
(defconstant operators "^*/+-")
(defconstant precedence '(-4 3 3 2 2))
Line 1,465:
(format t "~%INFIX:\"~A\"~%" expr)
(format t "RPN:\"~A\"~%" (rpn expr)))))
</syntaxhighlight>
</lang>
{{out}}
<pre>CL-USER(2): (main)
Line 1,498:
=={{header|D}}==
{{trans|Java}}
<langsyntaxhighlight Dlang="d">import std.container;
import std.stdio;
 
Line 1,587:
s.removeFront;
return v;
}</langsyntaxhighlight>
 
{{out}}
Line 1,594:
 
=={{header|EchoLisp}}==
<langsyntaxhighlight lang="scheme">
(require 'hash)
(require 'tree)
Line 1,647:
(writeln 'infix infix)
(writeln 'RPN (queue->list Q)))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,673:
 
=={{header|F_Sharp|F#}}==
<langsyntaxhighlight lang="fsharp">open System
 
type action = Shift | ReduceStack | ReduceInput
Line 1,767:
shunting_yard (State((Array.toList input), [], []))
|> (fun s -> s.report ReduceStack)
0</langsyntaxhighlight>
{{out}}
<pre> reduce [3] + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 1,808:
 
===Source===
<langsyntaxhighlight Fortranlang="fortran"> MODULE COMPILER !At least of arithmetic expressions.
INTEGER KBD,MSG !I/O units.
 
Line 2,041:
13 FORMAT (L6," RPN: >",A,"<")
GO TO 10
END</langsyntaxhighlight>
 
===Results===
Line 2,101:
===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...
<langsyntaxhighlight Fortranlang="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.
INTEGER OPSYMBOLS !Recognised operator symbols.
Line 2,148:
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 ^."),
5 SYMB("! ",15,1,"factorial, sortof, just for fun.")/))</langsyntaxhighlight>
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}}==
No error checking. No extra credit output, but there are some comments in the code.
<langsyntaxhighlight lang="go">package main
 
import (
Line 2,224:
}
return
}</langsyntaxhighlight>
Output:
<pre>
Line 2,235:
Simple with zero error handling; some extra credit.
 
<langsyntaxhighlight Haskelllang="haskell">import Text.Printf
 
prec :: String -> Int
Line 2,293:
z
)
$ simSYA $ words a</langsyntaxhighlight>
 
Output:
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.
 
<langsyntaxhighlight Haskelllang="haskell">{-# LANGUAGE LambdaCase #-}
import Control.Applicative
import Control.Lens
Line 2,415:
Left msg -> putStrLn msg >> main
Right ts -> putStrLn (showOutput (toRPN ts)) >> main
</syntaxhighlight>
</lang>
 
<pre>Enter expression: 3 + ( ( 4 + 5 )
Line 2,430:
 
=={{header|Icon}} and {{header|Unicon}}==
<langsyntaxhighlight Iconlang="icon">procedure main()
infix := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
printf("Infix = %i\n",infix)
Line 2,493:
every (s := "[ ") ||:= !L || " "
return s || "]"
end</langsyntaxhighlight>
 
{{libheader|Icon Programming Library}}
Line 2,523:
=={{header|J}}==
Code
<syntaxhighlight lang="j">
<lang J>
NB. j does not have a verb based precedence.
NB. j evaluates verb noun sequences from right to left.
Line 2,668:
 
fulfill_requirement=: ;@:(' '&,&.>)@:algebra_to_rpn
</syntaxhighlight>
</lang>
Demonstration
<syntaxhighlight lang="j">
<lang J>
fulfill_requirement '3+4*2/(1-5)^2^3'
3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 2,726:
OUTPUT queue ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
</syntaxhighlight>
</lang>
 
=={{header|Java}}==
{{works with|Java|7}}
<langsyntaxhighlight lang="java">import java.util.Stack;
 
public class ShuntingYard {
Line 2,788:
return sb.toString();
}
}</langsyntaxhighlight>
 
Output:
Line 2,796:
 
=={{header|JavaScript}}==
<langsyntaxhighlight lang="javascript">function Stack() {
this.dataStore = [];
this.top = 0;
Line 2,864:
}
postfix += s.dataStore.reverse().join(" ");
print(postfix);</langsyntaxhighlight>
 
Output:
Line 2,873:
=={{header|Julia}}==
Translation from the Wikipedia reference article's pseudocode.
<langsyntaxhighlight lang="julia">
function parseinfix2rpn(s)
outputq = []
Line 2,915:
teststring = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
println("\nResult: $teststring becomes $(join(parseinfix2rpn(teststring), ' '))")
</syntaxhighlight>
</lang>
{{output}}
<pre>
Line 2,939:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">// version 1.2.0
 
import java.util.Stack
Line 2,999:
println("Postfix : ${infixToPostfix(e)}\n")
}
}</langsyntaxhighlight>
 
{{out}}
Line 3,011:
 
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
<lang lb>
global stack$,queue$
stack$=""
Line 3,127:
wend
end function
</syntaxhighlight>
</lang>
 
{{out}}
Line 3,154:
 
=={{header|Lua}}==
<syntaxhighlight lang="lua">
<lang Lua>
-- Lua 5.3.5
-- Retrieved from: https://devforum.roblox.com/t/more-efficient-way-to-implement-shunting-yard/1328711
Line 3,254:
print('infix:', goodmath)
print('postfix:', shuntingYard(goodmath))
</syntaxhighlight>
</lang>
 
{{out}}
Line 3,308:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">rpn[str_] :=
StringRiffle[
ToString /@
Line 3,339:
While[stack != {}, AppendTo[out, stack[[-1]]];
stack = stack[[;; -2]]]; out]];
Print[rpn["3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]];</langsyntaxhighlight>
{{out}}
<pre>3 4 2 * 1 5 - / 2 3 ^ ^ +</pre>
 
=={{header|Nim}}==
<langsyntaxhighlight lang="nim">import tables, strutils, strformat
 
type operator = tuple[prec:int, rassoc:bool]
Line 3,388:
 
echo &"for infix expression: '{input}' \n", "\nTOKEN OP STACK RPN OUTPUT"
echo "postfix: ", shuntRPN(input.strip.split)</langsyntaxhighlight>
 
{{out}}
Line 3,417:
=={{header|OCaml}}==
{{works with|ocaml|4.04}}
<langsyntaxhighlight lang="ocaml">
type associativity = Left | Right;;
 
Line 3,477:
let postfix = shunting_yard tkns in
print_endline (intercalate " " postfix);;
</syntaxhighlight>
</lang>
 
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">my %prec = (
'^' => 4,
'*' => 3,
Line 3,530:
local $, = " ";
print shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
</syntaxhighlight>
</lang>
{{out}}
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 3,556:
=={{header|Phix}}==
{{Trans|Go}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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>
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) ^ 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 2 * 1 5 - 2 ^ /"</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 3,694:
=={{header|PicoLisp}}==
Note: "^" is a meta-character and must be escaped in strings
<langsyntaxhighlight PicoLisplang="picolisp">(de operator (Op)
(member Op '("\^" "*" "/" "+" "-")) )
 
Line 3,734:
(quit "Unbalanced Stack") )
(link (pop 'Stack))
(tab Fmt NIL (glue " " (made)) Stack) ) ) ) )</langsyntaxhighlight>
Output:
<langsyntaxhighlight PicoLisplang="picolisp">: (shuntingYard "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3")
Token Output Stack
3 3
Line 3,757:
3 4 2 * 1 5 - 2 3 ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
-> (3 4 2 "*" 1 5 "-" 2 3 "\^" "\^" "/" "+")</langsyntaxhighlight>
 
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
<lang PL/I>
cvt: procedure options (main); /* 15 January 2012. */
declare (in, stack, out) character (100) varying;
Line 3,843:
 
end cvt;
</syntaxhighlight>
</lang>
Output:
<syntaxhighlight lang="text">
INPUT STACK OUTPUT
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) (
Line 3,878:
3 4 2 * 1 5 - 2 3 ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
</syntaxhighlight>
</lang>
 
=={{header|Python}}==
Parenthesis are added to the operator table then special-cased in the code.
This solution includes the extra credit.
<langsyntaxhighlight lang="python">from collections import namedtuple
from pprint import pprint as pp
 
Line 3,985:
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])</langsyntaxhighlight>
 
;Sample output:
Line 4,017:
 
=={{header|Racket}}==
<syntaxhighlight lang="racket">
<lang Racket>
#lang racket
;print column of width w
Line 4,062:
((if (lasso? x) <= <) (prec x) (prec y)))))])
(shunt (append (reverse l) out) (cons x r) in (format "out ~a, push ~a" l x)))])])))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 4,087:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>
<lang perl6>
my %prec =
'^' => 4,
Line 4,134:
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
</syntaxhighlight>
</lang>
{{out}}
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 4,161:
These REXX versions below allow multi-character tokens &nbsp; (both operands and operators).
===assume expression is correct===
<langsyntaxhighlight lang="rexx">/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/
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.*/
Line 4,212:
/*──────────────────────────────────────────────────────────────────────────────────────────*/
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</langsyntaxhighlight>
'''output''' &nbsp; when using the default input:
<pre>
Line 4,252:
 
The &nbsp; '''select''' &nbsp; group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source.
<langsyntaxhighlight lang="rexx">/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/
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.*/
Line 4,308:
/*──────────────────────────────────────────────────────────────────────────────────────────*/
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</langsyntaxhighlight>
'''output''' &nbsp; when using the input: <tt> ) &nbsp; ( </tt>
<pre>
Line 4,318:
See [[Parsing/RPN/Ruby]]
 
<langsyntaxhighlight lang="ruby">rpn = RPNExpression.from_infix("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")</langsyntaxhighlight>
outputs
<pre>for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 4,342:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">type Number = f64;
 
#[derive(Debug, Copy, Clone, PartialEq)]
Line 4,501:
 
calculate(postfix_tokens)
}</langsyntaxhighlight>
 
=={{header|Sidef}}==
{{trans|Raku}}
<langsyntaxhighlight lang="ruby">var prec = Hash(
'^' => 4,
'*' => 3,
Line 4,562:
}
 
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ')</langsyntaxhighlight>
{{out}}
<pre>
Line 4,589:
 
=={{header|Standard ML}}==
<langsyntaxhighlight lang="sml">structure Operator = struct
datatype associativity = LEFT | RIGHT
type operator = { symbol : char, assoc : associativity, precedence : int }
Line 4,698:
parse' tokens [] []
end
end</langsyntaxhighlight>
 
=={{header|Swift}}==
<langsyntaxhighlight Swiftlang="swift">import Foundation
 
// Using arrays for both stack and queue
Line 4,876:
print("input: \(input)")
print("output: \(output)")
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 4,884:
 
=={{header|Tcl}}==
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
 
# Helpers
Line 4,941:
}
 
puts [shunting "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]</langsyntaxhighlight>
Output:
<pre>
Line 4,998:
=={{header|UNIX Shell}}==
 
<langsyntaxhighlight lang="bash">#!/bin/sh
 
getopprec() {
Line 5,100:
}
 
infix 3 + 4 \* 2 / \( 1 - 5 \) ^ 2 ^ 3</langsyntaxhighlight>
 
===Output===
<syntaxhighlight lang="text">Token: 3
Output: 3
Operators:
Line 5,150:
End parsing
Output: 3 4 2 1 5 - 2 3 ^ ^ / * +
Operators:</langsyntaxhighlight>
 
=={{header|VBA}}==
Line 5,156:
{{trans|Liberty BASIC}}
 
<langsyntaxhighlight VBAlang="vba">Option Explicit
Option Base 1
 
Line 5,265:
Function Peek(stack)
Peek = stack(UBound(stack))
End Function</langsyntaxhighlight>
 
{{out}}
Line 5,290:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Module Module1
Class SymbolType
Public ReadOnly symbol As String
Line 5,372:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>3: stack[ ] out[ 3 ]
Line 5,396:
{{libheader|Wren-seq}}
{{libheader|Wren-pattern}}
<langsyntaxhighlight lang="ecmascript">import "/seq" for Stack
import "/pattern" for Pattern
 
Line 5,447:
System.print("Infix : %(e)")
System.print("Postfix : %(infixToPostfix.call(e))\n")
}</langsyntaxhighlight>
 
{{out}}
Line 5,462:
{{trans|VBA}}
 
<syntaxhighlight lang="xojo">
<lang Xojo>
 
Function ShuntingYard(strInfix As String) As String
Line 5,633:
 
End Function</langsyntaxhighlight>
 
 
Line 5,661:
=={{header|zkl}}==
{{trans|Go}}
<langsyntaxhighlight lang="zkl">var input="3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
var opa=Dictionary("^",T(4,True), "*",T(3,False), // op:(prec,rAssoc)
Line 5,711:
"Queue|".println(rpn);
println();
}</langsyntaxhighlight>
{{out}}
<pre style="height:20ex;overflow:scroll;">
10,333

edits