Parsing/Shunting-yard algorithm: Difference between revisions
Add Scala implementation
(Add Scala implementation) |
|||
| (9 intermediate revisions by 5 users not shown) | |||
Line 43:
{{trans|Java}}
<
-V ops = ‘-+/*^’
V sb = ‘’
Line 85:
V infix = ‘3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3’
print(‘infix: ’infix)
print(‘postfix: ’infix_to_postfix(infix))</
{{out}}
Line 94:
=={{header|8th}}==
<
\ https://en.wikipedia.org/wiki/Shunting-yard_algorithm
Line 224:
"Expected: \n" . "3 4 2 * 1 5 - 2 3 ^ ^ / +" . cr
bye
</syntaxhighlight>
{{out}}
<pre>NUMBER 3
Line 293:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<
# 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</
{{out}}
<pre>
Line 394:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
#NoEnv
Line 463:
Space(n){
return n>0 ? A_Space Space(n-1) : ""
}</
;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.
<
#include <regex.h>
#include <stdio.h>
Line 677:
return 0;
}</
;Output:
Line 816:
=={{header|C sharp}}==
{{works with|C sharp|7.0}}
<
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)} ]");
}
}</
{{out}}
<pre>
Line 921:
clang++ -Wall -pedantic-errors -O3 -std=c++17 a.cpp
<
#include <iostream>
#include <regex>
Line 1,139:
std::cerr << "error: " << e.what() << "\n";
return 1;
}</
{{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}}
<
#include <sstream>
#include <stack>
Line 1,234:
return 0;
}</
{{out}}
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 1,240:
=={{header|Ceylon}}==
<
ArrayList
Line 1,345:
assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +");
print("\nthe result is ``rpn``");
}</
{{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.
<
(defconstant operators "^*/+-")
(defconstant precedence '(-4 3 3 2 2))
Line 1,465:
(format t "~%INFIX:\"~A\"~%" expr)
(format t "RPN:\"~A\"~%" (rpn expr)))))
</syntaxhighlight>
{{out}}
<pre>CL-USER(2): (main)
Line 1,498:
=={{header|D}}==
{{trans|Java}}
<
import std.stdio;
Line 1,587:
s.removeFront;
return v;
}</
{{out}}
Line 1,594:
=={{header|EchoLisp}}==
<
(require 'hash)
(require 'tree)
Line 1,647:
(writeln 'infix infix)
(writeln 'RPN (queue->list Q)))
</syntaxhighlight>
{{out}}
<pre>
Line 1,673:
=={{header|F_Sharp|F#}}==
<
type action = Shift | ReduceStack | ReduceInput
Line 1,767:
shunting_yard (State((Array.toList input), [], []))
|> (fun s -> s.report ReduceStack)
0</
{{out}}
<pre> reduce [3] + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 1,808:
===Source===
<
INTEGER KBD,MSG !I/O units.
Line 2,041:
13 FORMAT (L6," RPN: >",A,"<")
GO TO 10
END</
===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...
<
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.")/))</
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.
<
import (
Line 2,224:
}
return
}</
Output:
<pre>
Line 2,235:
Simple with zero error handling; some extra credit.
<
prec :: String -> Int
Line 2,293:
z
)
$ simSYA $ words a</
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.
<
import Control.Applicative
import Control.Lens
Line 2,415:
Left msg -> putStrLn msg >> main
Right ts -> putStrLn (showOutput (toRPN ts)) >> main
</syntaxhighlight>
<pre>Enter expression: 3 + ( ( 4 + 5 )
Line 2,430:
=={{header|Icon}} and {{header|Unicon}}==
<
infix := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
printf("Infix = %i\n",infix)
Line 2,493:
every (s := "[ ") ||:= !L || " "
return s || "]"
end</
{{libheader|Icon Programming Library}}
Line 2,523:
=={{header|J}}==
Code
<syntaxhighlight 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>
Demonstration
<syntaxhighlight 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>
=={{header|Java}}==
{{works with|Java|7}}
<
public class ShuntingYard {
Line 2,788:
return sb.toString();
}
}</
Output:
Line 2,796:
=={{header|JavaScript}}==
<
this.dataStore = [];
this.top = 0;
Line 2,864:
}
postfix += s.dataStore.reverse().join(" ");
print(postfix);</
Output:
Line 2,873:
=={{header|Julia}}==
Translation from the Wikipedia reference article's pseudocode.
<
function parseinfix2rpn(s)
outputq = []
Line 2,915:
teststring = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
println("\nResult: $teststring becomes $(join(parseinfix2rpn(teststring), ' '))")
</syntaxhighlight>
{{output}}
<pre>
Line 2,939:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.Stack
Line 2,999:
println("Postfix : ${infixToPostfix(e)}\n")
}
}</
{{out}}
Line 3,011:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
global stack$,queue$
stack$=""
Line 3,127:
wend
end function
</syntaxhighlight>
{{out}}
Line 3,154:
=={{header|Lua}}==
<syntaxhighlight 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>
{{out}}
Line 3,308:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
StringRiffle[
ToString /@
Line 3,339:
While[stack != {}, AppendTo[out, stack[[-1]]];
stack = stack[[;; -2]]]; out]];
Print[rpn["3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]];</
{{out}}
<pre>3 4 2 * 1 5 - / 2 3 ^ ^ +</pre>
=={{header|Nim}}==
<
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)</
{{out}}
Line 3,417:
=={{header|OCaml}}==
{{works with|ocaml|4.04}}
<
type associativity = Left | Right;;
Line 3,477:
let postfix = shunting_yard tkns in
print_endline (intercalate " " postfix);;
</syntaxhighlight>
=={{header|Perl}}==
{{trans|Raku}}
<
'^' => 4,
'*' => 3,
Line 3,530:
local $, = " ";
print shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
</syntaxhighlight>
{{out}}
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 3,556:
=={{header|Phix}}==
{{Trans|Go}}
<!--<
<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>
<!--</
{{out}}
<pre>
Line 3,694:
=={{header|PicoLisp}}==
Note: "^" is a meta-character and must be escaped in strings
<
(member Op '("\^" "*" "/" "+" "-")) )
Line 3,734:
(quit "Unbalanced Stack") )
(link (pop 'Stack))
(tab Fmt NIL (glue " " (made)) Stack) ) ) ) )</
Output:
<
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 "\^" "\^" "/" "+")</
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
cvt: procedure options (main); /* 15 January 2012. */
declare (in, stack, out) character (100) varying;
Line 3,843:
end cvt;
</syntaxhighlight>
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>
=={{header|Python}}==
Parenthesis are added to the operator table then special-cased in the code.
This solution includes the extra credit.
<
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])</
;Sample output:
Line 4,017:
=={{header|Racket}}==
<syntaxhighlight 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>
{{out}}
<pre>
Line 4,087:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line> my %prec =
'^' => 4,
my %assoc =
'^' => 'right',
sub shunting-yard ($prog) {
my @inp = $prog.words;
sub report($op) { printf "%25s %-7s %10s %s\n", ~@res, ~@ops, $op, ~@inp }
while @inp {
default {
last
reduce
shift
reduce @ops.pop while @ops;
@res;
}
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';</syntaxhighlight>
{{out}}
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 4,161 ⟶ 4,159:
These REXX versions below allow multi-character tokens (both operands and operators).
===assume expression is correct===
<
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 ⟶ 4,210:
/*──────────────────────────────────────────────────────────────────────────────────────────*/
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</
'''output''' when using the default input:
<pre>
Line 4,252 ⟶ 4,250:
The '''select''' group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source.
<
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 ⟶ 4,306:
/*──────────────────────────────────────────────────────────────────────────────────────────*/
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</
'''output''' when using the input: <tt> ) ( </tt>
<pre>
input: ) (
RPN──► ─────── error in expression ───────
</pre>
=={{header|RPL}}==
≪ "§" + → expression
≪ { }
1 expression SIZE '''FOR''' j
DUP TYPE NOT <span style="color:grey">@ 1 if a number is in top-stack position</span>
expression j DUP SUB
'''IF''' "0123456789" OVER POS '''THEN'''
STR→
'''IF''' SWAP '''THEN''' SWAP 10 * + '''END'''
'''ELSE'''
'''IF''' SWAP '''THEN''' ROT ROT + SWAP '''END'''
'''IF''' "^*/+-()" OVER POS '''THEN''' + '''ELSE''' DROP '''END'''
'''END'''
'''NEXT'''
≫ ≫ ‘<span style="color:blue">LEXER</span>’ STO <span style="color:grey">@ ( "1+(2*3)" → { 1 "+" "(" 2 "*" 3 ")" } )</span>
≪ '''IF''' OVER '''THEN'''
"^*/+-" DUP 5 PICK POS SWAP ROT POS
{ 4 3 3 2 2 } { 1 0 0 0 0 }
→ o2 o1 prec rasso
≪ '''IF''' o2 '''THEN'''
prec o1 GET prec o2 GET
'''IF''' rasso o1 GET '''THEN''' < '''ELSE''' ≤ '''END'''
'''ELSE''' 0 '''END'''
≫
'''ELSE''' DROP 0 '''END'''
≫ ‘<span style="color:blue">POPOP?</span>’ STO <span style="color:grey">@ ( op → Boolean )</span>
≪ <span style="color:blue">LEXER</span> { } "" → infix postfix token
≪ 0
1 infix SIZE '''FOR''' j
infix j GET 'token' STO
1 SF
'''CASE'''
"^*/+-" token →STR POS '''THEN'''
1 CF
'''WHILE''' token <span style="color:blue">POPOP?</span> '''REPEAT'''
'postfix' ROT STO+ 1 - '''END'''
token SWAP 1 + '''END'''
"(" token == '''THEN'''
token SWAP 1 + '''END'''
")" token == '''THEN'''
'''WHILE''' DUP 1 FS? AND '''REPEAT'''
'''IF''' OVER "(" ≠ '''THEN'''
'postfix' ROT STO+
'''ELSE''' SWAP DROP 1 CF '''END'''
1 -
'''END'''
'''END'''
1 FS? '''THEN''' 'postfix' token STO+ '''END'''
'''END'''
'''NEXT'''
'''WHILE''' DUP '''REPEAT'''
'postfix' ROT STO+
1 - '''END'''
DROP ""
1 postfix SIZE '''FOR''' j
postfix j GET + " " + '''NEXT'''
≫ ≫ ‘<span style="color:blue">→RPN<span>’ STO
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" <span style="color:blue">→RPN<span>
{{out}}
<pre>
1: "3 4 2 * 1 5 - 2 3 ^ ^ / + "
</pre>
Line 4,318 ⟶ 4,382:
See [[Parsing/RPN/Ruby]]
<
outputs
<pre>for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 4,342 ⟶ 4,406:
=={{header|Rust}}==
<
#[derive(Debug, Copy, Clone, PartialEq)]
Line 4,501 ⟶ 4,565:
calculate(postfix_tokens)
}</
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import scala.util.control.Breaks._
object ShuntingYard {
def main(args: Array[String]): Unit = {
val infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
println(s"infix: $infix")
println(s"postfix: ${infixToPostfix(infix)}")
}
def infixToPostfix(infix: String): String = {
val ops = "-+/*^"
val sb = new StringBuilder
val s = scala.collection.mutable.Stack[Int]()
infix.split("\\s").foreach { token =>
if (token.nonEmpty) {
val c = token.head
val idx = ops.indexOf(c)
if (idx != -1) {
if (s.isEmpty) s.push(idx)
else {
breakable({
while (s.nonEmpty) {
val prec2 = s.top / 2
val prec1 = idx / 2
if (prec2 > prec1 || (prec2 == prec1 && c != '^')) sb.append(ops(s.pop)).append(' ')
else break
}
});
s.push(idx)
}
} else if (c == '(') {
s.push(-2) // -2 stands for '('
} else if (c == ')') {
// until '(' on stack, pop operators.
while (s.top != -2) sb.append(ops(s.pop)).append(' ')
s.pop()
} else {
sb.append(token).append(' ')
}
}
}
while (s.nonEmpty) sb.append(ops(s.pop)).append(' ')
sb.toString
}
}
</syntaxhighlight>
{{out}}
<pre>
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
</pre>
=={{header|Sidef}}==
{{trans|Raku}}
<
'^' => 4,
'*' => 3,
Line 4,562 ⟶ 4,686:
}
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ')</
{{out}}
<pre>
Line 4,589 ⟶ 4,713:
=={{header|Standard ML}}==
<
datatype associativity = LEFT | RIGHT
type operator = { symbol : char, assoc : associativity, precedence : int }
Line 4,698 ⟶ 4,822:
parse' tokens [] []
end
end</
=={{header|Swift}}==
<syntaxhighlight lang="swift">// Updated to Swift 5.7
import Foundation
// Using arrays for both stack and queue
struct Stack<T> {
var isEmpty: Bool {
elements.isEmpty
}
var top: T? {
elements.last
}
mutating func push(_ newElement: T) {
elements.append(newElement)
}
mutating func pop() -> T? {
self.isEmpty ? nil : elements.removeLast()
}
}
struct Queue<T> {
var isEmpty: Bool {
elements.isEmpty
}
mutating func enqueue(_ newElement: T) {
elements.append(newElement)
}
mutating func dequeue() -> T {
return elements.removeFirst()
}
}
enum Associativity {
case Left, Right
}
// Protocol can be used to restrict Set extension
protocol OperatorType: Comparable, Hashable {
}
struct Operator: OperatorType {
// Duplicate operator names are not allowed
func hash(into hasher: inout Hasher) {
hasher.combine(self.name)
}
init(_ name: String, _ precedence: Int, _ associativity: Associativity) {
self.name = name; self.precedence = precedence; self.associativity = associativity
}
}
func ==(x: Operator, y: Operator) -> Bool {
// Identified by name
}
func <(x: Operator, y: Operator) -> Bool {
}
extension Set where Element: OperatorType {
contains { $0.name
}
subscript (operatorName: String) -> Element? {
get {
filter { $0.name == operatorName }.first
}
}
}
// Convenience
extension String {
}
struct ShuntingYard {
case MismatchedParenthesis(parenthesis: String, expression: String)
case UnrecognizedToken(token: String, expression: String)
case ExtraneousToken(token: String, expression: String)
}
static func parse(_ input: String, operators: Set<Operator>) throws -> String {
var output = Queue<String>()
let tokens = input.components(separatedBy: " ")
for token in tokens {
// Number?
if token.isNumber {
// Add it to the output queue
output.enqueue(token)
continue
}
// Operator?
if operators.contains(token) {
// While there is a operator on top of the stack and has lower precedence than current operator (token)
while let top = stack.top,
operators.contains(top) && Self.hasLowerPrecedence(token, top, operators) {
// Pop it off to the output queue
output.enqueue(stack.pop()!)
}
// Push current operator (token) onto the operator stack
stack.push(token)
continue
}
// Left parenthesis?
if token == "(" {
// Push it onto the stack
stack.push(token)
continue
}
// Right parenthesis?
if token == ")" {
// Until the token at the top of the stack is a left parenthesis
while let top = stack.top, top != "(" {
// Pop operators off the stack onto the output queue.
output.enqueue(stack.pop()!)
}
// Pop the left parenthesis from the stack without putting it onto the output queue
guard let _ = stack.pop() else {
// If the stack runs out, than there is no matching left parenthesis
throw ParseError.MismatchedParenthesis(parenthesis: ")", expression: input)
}
continue
}
// Token not recognized!
throw ParseError.UnrecognizedToken(token: token, expression: token)
}
// No more tokens
// Still operators on the stack?
while let top = stack.top,
operators.contains(top) {
// Put them onto the output queue
output.enqueue(stack.pop()!)
}
// If the top of the stack is a (left) parenthesis, then there is no matching right parenthesis
// Note: Assume that all operators has been popped and put onto the output queue
if let top = stack.pop() {
throw (
top == "("
? ParseError.MismatchedParenthesis(parenthesis: "(", expression: input)
: ParseError.ExtraneousToken(token: top, expression: input)
)
}
return output.elements.joined(separator: " ")
}
static private func hasLowerPrecedence(_ firstToken: String, _ secondToken: String, _ operators: Set<Operator>) -> Bool {
guard let firstOperator = operators[firstToken],
let secondOperator = operators[secondToken] else {
return false
}
return firstOperator < secondOperator
}
}
/* Include in tests
func testParse() throws {
let input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
let operators:
Operator("+", 2, .Left),
Operator("-", 2, .Left)
]
let output = try! ShuntingYard.parse(input, operators: operators)
XCTAssertEqual(output, "3 4 2 * 1 5 - 2 3 ^ ^ / +")
}
*/
</syntaxhighlight>
{{out}}
<pre>
Line 4,884 ⟶ 5,033:
=={{header|Tcl}}==
<
# Helpers
Line 4,941 ⟶ 5,090:
}
puts [shunting "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]</
Output:
<pre>
Line 4,998 ⟶ 5,147:
=={{header|UNIX Shell}}==
<
getopprec() {
Line 5,100 ⟶ 5,249:
}
infix 3 + 4 \* 2 / \( 1 - 5 \) ^ 2 ^ 3</
===Output===
<syntaxhighlight lang="text">Token: 3
Output: 3
Operators:
Line 5,150 ⟶ 5,299:
End parsing
Output: 3 4 2 1 5 - 2 3 ^ ^ / * +
Operators:</
=={{header|VBA}}==
Line 5,156 ⟶ 5,305:
{{trans|Liberty BASIC}}
<
Option Base 1
Line 5,265 ⟶ 5,414:
Function Peek(stack)
Peek = stack(UBound(stack))
End Function</
{{out}}
Line 5,290 ⟶ 5,439:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Class SymbolType
Public ReadOnly symbol As String
Line 5,372 ⟶ 5,521:
End Sub
End Module</
{{out}}
<pre>3: stack[ ] out[ 3 ]
Line 5,396 ⟶ 5,545:
{{libheader|Wren-seq}}
{{libheader|Wren-pattern}}
<
import "./pattern" for Pattern
/* To find out the precedence, we take the index of the
Line 5,447 ⟶ 5,596:
System.print("Infix : %(e)")
System.print("Postfix : %(infixToPostfix.call(e))\n")
}</
{{out}}
Line 5,462 ⟶ 5,611:
{{trans|VBA}}
<syntaxhighlight lang="xojo">
Function ShuntingYard(strInfix As String) As String
Line 5,633 ⟶ 5,782:
End Function</
Line 5,658 ⟶ 5,807:
Output:
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">int Stack(10);
int SP; \stack pointer
proc Push(N);
int N;
[Stack(SP):= N; SP:= SP+1];
func Pop;
[SP:= SP-1; return Stack(SP)];
func Precedence(Op);
int Op;
case Op of
^+, ^-: return 2;
^*, ^/: return 3;
^^: return 4
other [];
proc ShowStack;
int I;
[ChOut(0, 9\tab\);
for I:= 0 to SP-1 do
[ChOut(0, Stack(I)); ChOut(0, ^ )];
CrLf(0);
];
char Str;
int Token, Op1, Op2;
[Str:= "3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3 ";
SP:= 0;
Text(0, "Input Output Stack^m^j");
loop [repeat Token:= Str(0); Str:= Str+1;
until Token # ^ ; \skip space characters
if Token # $A0 \terminating space\ then
[ChOut(0, Token); ChOut(0, 9\tab\)];
case Token of
^+, ^-, ^*, ^/, ^^:
[Op1:= Token;
loop [if SP <= 0 then quit; \empty
Op2:= Stack(SP-1);
if Op2 = ^( then quit;
if Precedence(Op2) < Precedence(Op1) then quit;
if Precedence(Op2) = Precedence(Op1) then
if Op1 = ^^ then quit;
ChOut(0, Pop);
];
Push(Op1);
];
^(: Push(Token);
^): [while SP > 0 and Stack(SP-1) # ^( do
ChOut(0, Pop);
Pop; \discard left parenthesis
];
$A0: quit \terminating space with MSB set
other ChOut(0, Token); \print single digit number
ShowStack;
];
while SP > 0 do \print any remaining operators
[ChOut(0, 9\tab\);
ChOut(0, Pop);
ShowStack;
];
]</syntaxhighlight>
{{out}}
<pre>
Input Output Stack
3 3
+ +
4 4 +
* + *
2 2 + *
/ * + /
( + / (
1 1 + / (
- + / ( -
5 5 + / ( -
) - + /
^ + / ^
2 2 + / ^
^ + / ^ ^
3 3 + / ^ ^
^ + / ^
^ + /
/ +
+
</pre>
=={{header|zkl}}==
{{trans|Go}}
<
var opa=Dictionary("^",T(4,True), "*",T(3,False), // op:(prec,rAssoc)
Line 5,711 ⟶ 5,948:
"Queue|".println(rpn);
println();
}</
{{out}}
<pre style="height:20ex;overflow:scroll;">
| |||