neumachen
7/18/2016 - 2:25 AM

Reverse Polish Notation Calculator

Reverse Polish Notation Calculator

package main

import (
	"fmt"
	"strconv"
	"unicode"
	"unicode/utf8"
)

func skipSpaces(s []byte) []byte {
	c, w := utf8.DecodeRune(s)
	for w > 0 && unicode.IsSpace(c) {
		s = s[w:]
		c, w = utf8.DecodeRune(s)
	}
	return s
}

func readDigits(s []byte) (numStr, remain []byte) {
	numStr = s
	totalW := 0
	c, w := utf8.DecodeRune(s)
	for w > 0 && unicode.IsDigit(c) {
		s = s[w:]
		totalW += w
		c, w = utf8.DecodeRune(s)
	}
	return numStr[:totalW], s
}

func pop(stack []int) (int, []int) {
	return stack[len(stack)-1], stack[:len(stack)-1]
}

func eval(s []byte) {
	stack := make([]int, 0)
	var a, b int
	var token []byte

	fmt.Println("eval:", string(s))

	s = skipSpaces(s)
	for len(s) > 0 {
		c, w := utf8.DecodeRune(s)
		switch {
		case unicode.IsDigit(c):
			token, s = readDigits(s)
			num, err := strconv.Atoi(string(token))
			if err != nil {
				fmt.Println(err)
			} else {
				stack = append(stack, num)
			}
		case c == '+':
			b, stack = pop(stack)
			a, stack = pop(stack)
			stack = append(stack, a+b)
			s = s[w:]
		case c == '-':
			b, stack = pop(stack)
			a, stack = pop(stack)
			stack = append(stack, a-b)
			s = s[w:]
		case c == '*':
			b, stack = pop(stack)
			a, stack = pop(stack)
			stack = append(stack, a*b)
			s = s[w:]
		case c == '/':
			b, stack = pop(stack)
			a, stack = pop(stack)
			stack = append(stack, a/b)
			s = s[w:]
		case c == '%':
			b, stack = pop(stack)
			a, stack = pop(stack)
			stack = append(stack, a%b)
			s = s[w:]
		default:
			fmt.Println("unknown character:", c)
			s = s[w:]
		}
		s = skipSpaces(s)
	}

	fmt.Println("stack:", stack)
}

func main() {
	// 2 * 21 - 30 = 12
	eval([]byte("2 21 * 30-"))

	// 1 + ... + 10 = 55
	eval([]byte("1 2 3 4 5 6 7 8 9 10+++++++++"))
}