Menu

문서정보

Reverse Polish Notation 평가

역폴란드 표기(Reverse Polish Notation)를 따르는 수식을 평가하는 코드를 작성하라. 사용 할 수 있는 연산자는 +, -, *, /이다. 연산대상으로는 int를 사용 할 수 있다.

예제
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Stack을 이용한 구현

역폴란드 표기법 자체가 스택에 최적화 돼 있다.
package main

import (
	"errors"
	"fmt"
	"strconv"
)

type stack struct {
	buffer   []int
	size     int
	capacity int
}

func CreateStack(capacity int) stack {
	s := stack{}
	s.buffer = make([]int, capacity)
	s.capacity = capacity
	s.size = 0
	return s
}

func (s *stack) Push(v int) error {
	s.buffer[s.size] = v
	s.size++
	return nil
}

func (s *stack) Pop() (int, error) {
	if s.size == 0 {
		return 0, errors.New("None Elememt")
	}
	s.size--
	return s.buffer[s.size], nil
}

func (s stack) Info() {
	fmt.Println("Elements :", s.buffer[:s.size])
	fmt.Println("Size     :", s.size)
	fmt.Println("Cap      :", s.capacity)
}

func main() {
	val, _ := evalRPN("35+42+*")
	fmt.Println(val)
}

func evalRPN(token string) (int, error) {
	myStack := CreateStack(10)
	for i := 0; i < len(token); i++ {
		num, err := strconv.Atoi(string(token[i]))
		if err != nil {
			a, _ := myStack.Pop()
			b, _ := myStack.Pop()
			switch string(token[i]) {
			case "+":
				myStack.Push(a + b)
			case "-":
				myStack.Push(a - b)
			case "*":
				myStack.Push(a * b)
			case "/":
				myStack.Push(a / b)
			default:
				// Ignore
			}
		} else {
			myStack.Push(num)
		}
	}
	return myStack.Pop()
}

		
코드를 단순화 하기 위해서 에러처리는 하지 않았다.