Rosetta Code

Parsing/Shunting-yard algorithm: Difference between revisions

Page Discussion

Parsing/Shunting-yard algorithm (view source)

Revision as of 12:45, 1 February 2024

5,181 bytes added ,  3 months ago
Add Scala implementation
m (syntax highlighting fixup automation)
(Add Scala implementation)
 
(8 intermediate revisions by 5 users not shown)
Line 4,087:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line> my %prec =
'^' => 4,
my %prec =
'^*' => 43,
'*/' => 3,
'/+' => 32,
'+-' => 2,
'-(' => 2,1;
 
'(' => 1;
my %assoc =
'^' => 'right',
my %assoc =
'^*' => 'rightleft',
'*/' => 'left',
'/+' => 'left',
'+-' => 'left',;
 
'-' => 'left';
sub shunting-yard ($prog) {
my @inp = $prog.words;
sub shunting-yard ($prog) {
my @inp = $prog.wordsops;
my @opsres;
 
my @res;
sub report($op) { printf "%25s %-7s %10s %s\n", ~@res, ~@ops, $op, ~@inp }
sub reportshift($opt) { printfreport( "%25sshift %-7s %10s %s\n$t",); ~@res, ~@ops,.push: $op, ~@inpt }
sub shiftreduce($t) { report( "shiftreduce $t"); @opsres.push: $t }
 
sub reduce($t) { report("reduce $t"); @res.push: $t }
while @inp {
while given @inp.shift {
given @inp.shiftwhen /\d/ { reduce $_ };
when /\d/'(' { reduceshift $_ };
when ')' { while @ops and (my $x = @ops.pop and $x ne '(') { shiftreduce $_x } }
default {
when ')' { while @ops and (my $x = @ops.pop and $x ne '(') { reduce $x } }
default my $newprec = %prec{$_};
my $newprecwhile =@ops %prec{$_};
while @ops my $oldprec = %prec{@ops[*-1]};
last myif $oldprecnewprec => %prec{@ops[*-1]}$oldprec;
last if $newprec >== $oldprec and %assoc{$_} eq 'right';
reduce last if $newprec == $oldprec and %assoc{$_} eq 'right'@ops.pop;
reduce @ops.pop;}
shift }$_;
shift $_;}
}
}
reduce @ops.pop while @ops;
}
@res;
reduce @ops.pop while @ops;
}
@res;
 
}
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';</syntaxhighlight>
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
</syntaxhighlight>
{{out}}
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 4,313 ⟶ 4,311:
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,502 ⟶ 4,566:
calculate(postfix_tokens)
}</syntaxhighlight>
 
 
=={{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}}==
Line 4,701 ⟶ 4,825:
 
=={{header|Swift}}==
<syntaxhighlight lang="swift">import// FoundationUpdated to Swift 5.7
import Foundation
 
// Using arrays for both stack and queue
struct Stack<T> {
private(set) var elements = [T]()
var isEmpty: Bool { return elements.isEmpty }
var isEmpty: Bool {
 
elements.isEmpty
mutating func push(newElement: T) {
}
elements.append(newElement)
}
var top: T? {
 
elements.last
mutating func pop() -> T {
}
return elements.removeLast()
}
mutating func push(_ newElement: T) {
 
elements.append(newElement)
func top() -> T? {
}
return elements.last
}
mutating func pop() -> T? {
self.isEmpty ? nil : elements.removeLast()
}
}
 
struct Queue<T> {
private(set) var elements = [T]()
var isEmpty: Bool { return elements.isEmpty }
var isEmpty: Bool {
elements.isEmpty
}
mutating func enqueue(_ newElement: T) {
elements.append(newElement)
}
mutating func dequeue() -> T {
return elements.removeFirst()
}
}
 
enum Associativity {
mutating func enqueue(newElement: T) {
case Left, Right
elements.append(newElement)
}
 
mutating func dequeue() -> T {
return elements.removeFirst()
}
}
 
// Protocol can be used to restrict Set extension
enum Associativity { case Left, Right }
 
// Define abstract interface, which can be used to restrict Set extension
protocol OperatorType: Comparable, Hashable {
var name: String { get }
var precedence: Int { get }
var associativity: Associativity { get }
}
 
struct Operator: OperatorType {
let name: String
let precedence: Int
let associativity: Associativity
// same operator names are not allowed
// Duplicate operator names are not allowed
var hashValue: Int { return "\(name)".hashValue }
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
}
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
// same operator names are not allowed
return x.name == y.name
}
 
func <(x: Operator, y: Operator) -> Bool {
// compare operators by theirTake precedence and associavity into account
return (x.associativity == .Left && x.precedence == y.precedence) || x.precedence < y.precedence
}
 
extension Set where Element: OperatorType {
func contains(op_ operatorName: String?) -> Bool {
contains { $0.name guard let== operatorName = op else { return false }
}
return contains { $0.name == operatorName }
}
subscript (operatorName: String) -> Element? {
 
get {
subscript (operatorName: String) -> Element? {
filter { $0.name == operatorName }.first
get {
}
return filter { $0.name == operatorName }.first
}
}
}
}
 
// Convenience
extension String {
var isNumber: Bool { return Double(self) != nil }
}
 
struct ShuntingYard {
enum ErrorParseError: ErrorTypeError {
case MismatchedParenthesis(parenthesis: String, expression: String)
case MismatchedParenthesis(String)
case UnrecognizedToken(token: String, expression: String)
case UnrecognizedToken(String)
case ExtraneousToken(token: String, expression: String)
}
}
static func parse(_ input: String, operators: Set<Operator>) throws -> String {
var stack = Stack<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
static func parse(input: String, operators: Set<Operator>) throws -> String {
func testParse() throws {
var stack = Stack<String>()
let input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
var output = Queue<String>()
let operators: Set<Operator> = [
let tokens = input.componentsSeparatedByString(" ")
Operator("^", 4, .Right),
 
Operator("*", 3, .Left),
for token in tokens {
Operator("/", 3, .Left),
// Wikipedia: if token is a number add it to the output queue
Operator("+", 2, .Left),
if token.isNumber {
Operator("-", 2, .Left)
output.enqueue(token)
]
}
let output = try! ShuntingYard.parse(input, operators: operators)
// Wikipedia: else if token is a operator:
XCTAssertEqual(output, "3 4 2 * 1 5 - 2 3 ^ ^ / +")
else if operators.contains(token) {
// Wikipedia: while there is a operator on top of the stack and has lower precedence than current operator (token)
while operators.contains(stack.top()) && hasLowerPrecedence(token, stack.top()!, operators) {
// Wikipedia: pop it off to the output queue
output.enqueue(stack.pop())
}
// Wikipedia: push current operator (token) onto the operator stack
stack.push(token)
}
// Wikipedia: If the token is a left parenthesis, then push it onto the stack.
else if token == "(" {
stack.push(token)
}
// Wikipedia: If the token is a right parenthesis:
else if token == ")" {
// Wikipedia: Until the token at the top of the stack is a left parenthesis
while !stack.isEmpty && stack.top() != "(" {
// Wikipedia: pop operators off the stack onto the output queue.
output.enqueue(stack.pop())
}
 
// If the stack runs out, than there are mismatched parentheses.
if stack.isEmpty {
throw Error.MismatchedParenthesis(input)
}
 
// Wikipedia: Pop the left parenthesis from the stack, but not onto the output queue.
stack.pop()
}
// if token is not number, operator or a parenthesis, then is not recognized
else {
throw Error.UnrecognizedToken(token)
}
}
 
// Wikipedia: When there are no more tokens to read:
 
// Wikipedia: While there are still operator tokens in the stack:
while operators.contains(stack.top()) {
// Wikipedia: Pop the operator onto the output queue.
output.enqueue(stack.pop())
}
 
// Wikipedia: If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses
// Note: Assume that all operators has been poped onto the output queue.
if stack.isEmpty == false {
throw Error.MismatchedParenthesis(input)
}
 
return output.elements.joinWithSeparator(" ")
}
 
static private func containsOperator(stack: Stack<String>, _ operators: [String: NSDictionary]) -> Bool {
guard stack.isEmpty == false else { return false }
// Is there a matching operator in the operators set?
return operators[stack.top()!] != nil ? true : false
}
 
static private func hasLowerPrecedence(x: String, _ y: String, _ operators: Set<Operator>) -> Bool {
guard let first = operators[x], let second = operators[y] else { return false }
return first < second
}
}
*/
 
let input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
let operators: Set<Operator> = [
Operator("^", 4, .Right),
Operator("*", 3, .Left),
Operator("/", 3, .Left),
Operator("+", 2, .Left),
Operator("-", 2, .Left)
]
let output = try! ShuntingYard.parse(input, operators: operators)
 
print("input: \(input)")
print("output: \(output)")
</syntaxhighlight>
{{out}}
Line 5,396 ⟶ 5,545:
{{libheader|Wren-seq}}
{{libheader|Wren-pattern}}
<syntaxhighlight lang="ecmascriptwren">import "./seq" for Stack
import "./pattern" for Pattern
 
/* To find out the precedence, we take the index of the
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}}==
Aspen138
337

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328080...351352"