Skip to content

Instantly share code, notes, and snippets.

@six519
Last active July 25, 2018 12:36
Show Gist options
  • Save six519/bb34d3a2f1ce4f0b947a389aa4158996 to your computer and use it in GitHub Desktop.
Save six519/bb34d3a2f1ce4f0b947a389aa4158996 to your computer and use it in GitHub Desktop.
Evaluate Reverse Polish Notation & Shunting-yard Algorithm Sample Code (Golang)
package main
import (
"fmt"
"bufio"
"os"
"errors"
"unicode"
"strconv"
)
type Lexer struct {
Text string
}
func (lexer Lexer) GenerateToken() ([]string, error) {
var tokenArray []string
for x := 0; x < len(lexer.Text); x++ {
currentChar := string(lexer.Text[x])
if(currentChar == "\n" || currentChar == " ") {
//ignore newline and space
continue
} else if(unicode.IsDigit([]rune(currentChar)[0])) {
if(len(tokenArray) == 0) {
tokenArray = append(tokenArray, currentChar)
} else {
if(unicode.IsDigit([]rune(tokenArray[len(tokenArray) - 1])[0])) {
tokenArray[len(tokenArray) - 1] += currentChar
} else {
tokenArray = append(tokenArray, currentChar)
}
}
} else if(currentChar == "(" || currentChar == ")" || currentChar == "+" || currentChar == "-" || currentChar == "/" || currentChar == "*") {
if(currentChar == "+" || currentChar == "-" || currentChar == "/" || currentChar == "*") {
if(len(tokenArray) > 0) {
if(tokenArray[len(tokenArray)-1] == "+" || tokenArray[len(tokenArray)-1] == "-" || tokenArray[len(tokenArray)-1] == "/" || tokenArray[len(tokenArray)-1] == "*") {
return tokenArray, errors.New("Syntax Error")
}
}
}
tokenArray = append(tokenArray, currentChar)
} else {
return tokenArray, errors.New("Syntax Error")
}
}
return tokenArray, nil
}
type Parser struct {
TokenArray []string
}
func (parser *Parser) Parse() error {
precedences := map[string] int{"+": 0, "-": 0, "/": 1, "*": 1} //order of precedences
var operatorStack []string
var outputQueue []string
if(len(parser.TokenArray) > 0) {
if(parser.TokenArray[0] == "+" || parser.TokenArray[0] == "-" || parser.TokenArray[0] == "/" || parser.TokenArray[0] == "*") {
//syntax error if the first token is an operator
return errors.New("Syntax error")
}
if(parser.TokenArray[len(parser.TokenArray)-1] == "+" || parser.TokenArray[len(parser.TokenArray)-1] == "-" || parser.TokenArray[len(parser.TokenArray)-1] == "/" || parser.TokenArray[len(parser.TokenArray)-1] == "*") {
//syntax error if the last token is an operator
return errors.New("Syntax error")
}
//shunting-yard below
//While there are tokens to be read:
for len(parser.TokenArray) > 0 {
//Read a token
currentToken := parser.TokenArray[0]
parser.TokenArray = append(parser.TokenArray[:0], parser.TokenArray[1:]...) //pop the first element
if(unicode.IsDigit([]rune(currentToken)[0])) {
//If it's a number add it to queue
outputQueue = append(outputQueue, currentToken)
}
if(currentToken == "+" || currentToken == "-" || currentToken == "/" || currentToken == "*") {
//If it's an operator
for true {
if(len(operatorStack) > 0) {
if(precedences[operatorStack[len(operatorStack) - 1]] >= precedences[currentToken]) {
/*
While there's an operator on the top of the stack with greater precedence:
Pop operators from the stack onto the output queue
*/
outputQueue = append(outputQueue, operatorStack[len(operatorStack) - 1])
operatorStack = operatorStack[:len(operatorStack)-1]
} else {
break
}
} else {
break
}
}
//Push the current operator onto the stack
operatorStack = append(operatorStack, currentToken)
}
if(currentToken == "(") {
//If it's a left bracket push it onto the stack
operatorStack = append(operatorStack, currentToken)
}
if(currentToken == ")") {
//If it's a right bracket
if(len(operatorStack) > 0) {
for true {
if(operatorStack[len(operatorStack) - 1] != "(") {
/*
While there's not a left bracket at the top of the stack:
Pop operators from the stack onto the output queue.
*/
outputQueue = append(outputQueue, operatorStack[len(operatorStack) - 1])
operatorStack = operatorStack[:len(operatorStack)-1]
} else {
//Pop the left bracket from the stack and discard it
operatorStack = operatorStack[:len(operatorStack)-1]
break
}
if(len(operatorStack) == 0) {
return errors.New("Syntax error")
}
}
} else {
return errors.New("Syntax error")
}
}
}
for len(operatorStack) > 0 {
if(operatorStack[len(operatorStack) - 1] == "(") {
return errors.New("Syntax error")
}
//While there are operators on the stack, pop them to the queue
outputQueue = append(outputQueue, operatorStack[len(operatorStack) - 1])
operatorStack = operatorStack[:len(operatorStack)-1]
}
//now the outputQueue contains the reverse polish notation
//read reverse polish notation below
if(len(outputQueue) > 0) {
var stack []string
for len(outputQueue) > 0 {
currentToken := outputQueue[0]
outputQueue = append(outputQueue[:0], outputQueue[1:]...) //pop the first element
if(currentToken == "+" || currentToken == "-" || currentToken == "/" || currentToken == "*") {
//get right operand
rightOperand, _ := strconv.Atoi(stack[len(stack)-1])
stack = stack[:len(stack)-1]
//get left operand
leftOperand, _ := strconv.Atoi(stack[len(stack)-1])
stack = stack[:len(stack)-1]
var result int
if(currentToken == "+") {
//addition
result = leftOperand + rightOperand
} else if(currentToken == "-") {
//substraction
result = leftOperand - rightOperand
} else if(currentToken == "/") {
//division
result = leftOperand / rightOperand
} else {
//assuming multiplication
result = leftOperand * rightOperand
}
stack = append(stack, strconv.Itoa(result))
} else {
stack = append(stack, currentToken)
}
}
//print evaluated result
fmt.Println("> " + stack[0])
}
}
return nil
}
func main() {
/*
Sample Run
==========
> ((15/(7-(1+1)))*3)-(2+(1+1))
> 5
*/
for true {
reader := bufio.NewReader(os.Stdin)
fmt.Print("> ")
text, _ := reader.ReadString('\n')
//convert to token
lxr := Lexer{Text: text}
tokenArray, tokenErr := lxr.GenerateToken()
if(tokenErr != nil) {
fmt.Println("> " + tokenErr.Error())
} else {
//parse token
parser := Parser{TokenArray: tokenArray}
parseErr := parser.Parse()
if(parseErr != nil) {
fmt.Println("> " + parseErr.Error())
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment