Rosetta Code

Parsing/Shunting-yard algorithm: Difference between revisions

Page Discussion

Parsing/Shunting-yard algorithm (view source)

Revision as of 10:47, 17 October 2022

327 bytes removed ,  1 year ago
Improved and adapted to Swift 5.7
(Improved and adapted to Swift 5.7)
Line 4,705:
struct Stack<T> {
private(set) var elements = [T]()
var isEmpty: Bool { return elements.isEmpty }▼
▲ var isEmpty: Bool { return elements.isEmpty }
mutating func push(newElement: T) {▼
elements.append(newElement)isEmpty
}
mutatingvar func pop() ->top: T? {
return elements.removeLast()last
}
mutating func toppush()_ ->newElement: T?) {
return elements.lastappend(newElement)
}▼
mutating func pop() -> T? {
self.isEmpty ? nil : elements.removeLast()
}
}
Line 4,722 ⟶ 4,725:
struct Queue<T> {
private(set) var elements = [T]()
var isEmpty: Bool { return elements.isEmpty }▼
▲ var isEmpty: Bool { return elements.isEmpty }
▲ mutating func enqueue(newElement: T) {
elements.isEmpty
}
▲ mutating func pushenqueue(_ newElement: T) {
elements.append(newElement)
}
Line 4,733 ⟶ 4,739:
}
 
enum Associativity { case Left, Right }
case Left, Right
}
 
// Define abstract interface, whichProtocol can be used to restrict Set extension
protocol OperatorType: Comparable, Hashable {
var name: String { get }
Line 4,746 ⟶ 4,754:
let precedence: Int
let associativity: Associativity
// sameDuplicate operator names are not allowed
func hash(into hasher: inout Hasher) {
hasher.combine(self.name)
Line 4,757 ⟶ 4,766:
 
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 {
return contains { $0.name == operatorName }▼
guard let operatorName = op else { return false }
▲ return contains { $0.name == operatorName }
}
subscript (operatorName: String) -> Element? {
get {
return filter { $0.name == operatorName }.first
}
}
Line 4,785 ⟶ 4,793:
 
struct ShuntingYard {
enum ShuntingYardErrorParseError: Error {
case MismatchedParenthesis(parenthesis: String, expression: String)
case UnrecognizedToken(token: String, expression: String)
case ExtraneousToken(token: String, expression: String)
}
Line 4,794 ⟶ 4,803:
var output = Queue<String>()
let tokens = input.components(separatedBy: " ")
let operatorNames = operators.map({ $0.name }).joined(separator: " ")
for token in tokens {
// Number?
// if token is a number add it to the output queue
if token.isNumber {
// Add it to the output.enqueue(newElement: token)queue
output.enqueue(token)
continue
}
}▼
// else if token is a operator:
// Operator?
else if operatorNamesoperators.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(),
operatorNames operators.contains(top) && Self.hasLowerPrecedence(token, top, operators) {
&& Self.hasLowerPrecedence(token, top, operators) {
// Pop it off to the output queue
output.enqueue(newElement: stack.pop()!)
}
// Push current operator (token) onto the operator stack
stack.push(newElement: token)
continue
}
// If the token is a left parenthesis, then push it onto the stack.
// If the token is a rightLeft parenthesis:?▼
else if token == "(" {▼
stack.push(newElement:if token) == "(" {
// Push it onto the stack
let _ = stack.poppush(token)▼
continue
}
▲ // If the token is a right parenthesis:
// Right parenthesis?
else if token == ")" {
▲ else if token == "()" {
// Until the token at the top of the stack is a left parenthesis
while !stack.isEmptylet &&top = stack.top(), top != "(" {
// Pop operators off the stack onto the output queue.
output.enqueue(newElement: stack.pop()!)
}
// IfPop the left parenthesis from the stack runswithout out,putting thanit thereonto arethe mismatchedoutput parentheses.queue
ifguard let _ = stack.isEmptypop() else {
// If the stack runs out, than there is no matching left parenthesis
throw ShuntingYardErrorParseError.MismatchedParenthesis(parenthesis: ")", expression: input)
}
continue
// Pop the left parenthesis from the stack, but not onto the output queue.
▲ let _ = stack.pop()
▲ }
// if token is not number, operator or a parenthesis, then it is not recognized
else {
throw ShuntingYardError.UnrecognizedToken(token)▼
}
// Token not recognized!
▲ throw ShuntingYardErrorParseError.UnrecognizedToken(token: token, expression: token)
}
// When there are noNo more tokens to read:
// WhileStill thereoperators are still operator tokens inon the stack:?
while let top = stack.top(),
operatorNames operators.contains(top) {
// PopPut the operatorthem onto the output queue.
output.enqueue(newElement: stack.pop()!)
}
// If the operator token on the top of the stack is a (left) parenthesis, then there areis mismatchedno parenthesesmatching right parenthesis
// Note: Assume that all operators has been popedpopped and put onto the output queue.
if stack.isEmptylet top == falsestack.pop() {
throw (
throw ShuntingYardError.MismatchedParenthesis(input)
top == "("
? ParseError.MismatchedParenthesis(parenthesis: "(", expression: input)
: ParseError.ExtraneousToken(token: top, expression: input)
)
}
Line 4,857 ⟶ 4,875:
}
static private func containsOperatorhasLowerPrecedence(stack_ firstToken: Stack<String>, _ operatorssecondToken: [String, _ operators: NSDictionary]Set<Operator>) -> Bool {
guard let firstOperator = operators[firstToken],
guard stack.isEmpty == false else { return false }
let secondOperator = operators[secondToken] else {
// Is there a matching operator in the operators set?
return operators[stack.top()!] != nil ? true : false
}
▲
return firstOperator < secondOperator
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
}
}
Papillo
2

edits

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