Last active
July 25, 2018 12:36
-
-
Save six519/bb34d3a2f1ce4f0b947a389aa4158996 to your computer and use it in GitHub Desktop.
Evaluate Reverse Polish Notation & Shunting-yard Algorithm Sample Code (Golang)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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