Parsing/Shunting-yard algorithm: Difference between revisions
Content deleted Content added
Added PicoLisp |
Go solution |
||
Line 450: | Line 450: | ||
Testing string `123' <enter> |
Testing string `123' <enter> |
||
^C</pre> |
^C</pre> |
||
=={{header|Go}}== |
|||
No error checking. No extra credit output, but there are some comments in the code. |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"strings" |
|||
) |
|||
var input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" |
|||
var opa = map[string]struct { |
|||
prec int |
|||
rAssoc bool |
|||
}{ |
|||
"^": {4, true}, |
|||
"*": {3, false}, |
|||
"/": {3, false}, |
|||
"+": {2, false}, |
|||
"-": {2, false}, |
|||
} |
|||
func main() { |
|||
fmt.Println("infix: ", input) |
|||
fmt.Println("postfix:", parseInfix(input)) |
|||
} |
|||
func parseInfix(e string) (rpn string) { |
|||
var stack []string // holds operators and left parenthesis |
|||
for _, tok := range strings.Fields(e) { |
|||
switch tok { |
|||
case "(": |
|||
stack = append(stack, tok) // push "(" to stack |
|||
case ")": |
|||
var op string |
|||
for { |
|||
// pop item ("(" or operator) from stack |
|||
op, stack = stack[len(stack)-1], stack[:len(stack)-1] |
|||
if op == "(" { |
|||
break // discard "(" |
|||
} |
|||
rpn += " " + op // add operator to result |
|||
} |
|||
default: |
|||
if o1, isOp := opa[tok]; isOp { |
|||
// token is an operator |
|||
for len(stack) > 0 { |
|||
// consider top item on stack |
|||
op := stack[len(stack)-1] |
|||
if o2, isOp := opa[op]; !isOp || o1.prec > o2.prec || |
|||
o1.prec == o2.prec && o1.rAssoc { |
|||
break |
|||
} |
|||
// top item is an operator that needs to come off |
|||
stack = stack[:len(stack)-1] // pop it |
|||
rpn += " " + op // add it to result |
|||
} |
|||
// push operator (the new one) to stack |
|||
stack = append(stack, tok) |
|||
} else { // token is an operand |
|||
if rpn > "" { |
|||
rpn += " " |
|||
} |
|||
rpn += tok // add operand to result |
|||
} |
|||
} |
|||
} |
|||
// drain stack to result |
|||
for len(stack) > 0 { |
|||
rpn += " " + stack[len(stack)-1] |
|||
stack = stack[:len(stack)-1] |
|||
} |
|||
return |
|||
}</lang> |
|||
Output: |
|||
<pre> |
|||
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
|||
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + |
|||
</pre> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |