Parsing/Shunting-yard algorithm: Difference between revisions
→{{header|Swift}}
Thundergnat (talk | contribs) m (→{{header|Raku}}: Undo bizarre single space indent that somebody found necessary to do) |
|||
Line 4,699:
=={{header|Swift}}==
<syntaxhighlight lang="swift">
import Foundation
// Using arrays for both stack and queue
struct Stack<T> {
}
}
}
}
struct Queue<T> {
}
}
}
Line 4,736 ⟶ 4,737:
// Define abstract interface, which can be used to restrict Set extension
protocol OperatorType: Comparable, Hashable {
}
struct Operator: OperatorType {
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 {
}
func <(x: Operator, y: Operator) -> Bool {
}
extension Set where Element: OperatorType {
}
}
}
}
// Convenience
extension String {
}
struct ShuntingYard {
}
static func parse(_ input: String, operators: Set<Operator>) throws -> String {
var stack = Stack<String>()
var output = Queue<String>()
let tokens = input.components(separatedBy: " ")
let operatorNames = operators.map({ $0.name }).joined(separator: " ")
for token in tokens {
// if token is a number add it to the output queue
if token.isNumber {
output.enqueue(newElement: token)
}
// else if token is a operator:
else if operatorNames.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.contains(top)
&& 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)
}
// If the token is a left parenthesis, then push it onto the stack.
else if token == "(" {
stack.push(newElement: token)
}
// If the token is a right parenthesis:
else if token == ")" {
// Until the token at the top of the stack is a left parenthesis
while !stack.isEmpty && stack.top() != "(" {
// Pop operators off the stack onto the output queue.
output.enqueue(newElement: stack.pop())
}
// If the stack runs out, than there are mismatched parentheses.
if stack.isEmpty {
throw ShuntingYardError.MismatchedParenthesis(input)
}
// 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)
}
}
// When there are no more tokens to read:
// While there are still operator tokens in the stack:
while let top = stack.top(),
operatorNames.contains(top) {
// Pop the operator onto the output queue.
output.enqueue(newElement: stack.pop())
}
// 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 ShuntingYardError.MismatchedParenthesis(input)
}
return output.elements.joined(separator: " ")
}
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
}
}
/* Include in tests
func testParse() throws {
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)
XCTAssertEqual(output, "3 4 2 * 1 5 - 2 3 ^ ^ / +")
}
*/
</syntaxhighlight>
{{out}}
| |||