|
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()) |
|
} |
|
} |
|
|
|
} |
|
} |