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

	}
}