Blog for Programming

1. 이론 이 알고리즘은 중위 표기법에서 후위 표기법으로 전환한 후에 후위표기법을 실질적으로 계산하는 알고리즘이다. 이 부분은 전에 포스팅한 중위 표기법의 후위 표기법 변환 알고리즘보다는 훨씬 간단하다. 예외와 구현이 나름 쉬웠다. 이 부분은 학교 수업으로 공부하였다. - 후위표기식의 계산 알고리즘 후위표기식의 계산 알고리즘은 다음과 같다. 숫자가 나오면 무조건 스택에 Push 연산자가 나오면 스택에서 두개의 피연산자를 꺼내 계산한다. 연산자가 뺄셈 혹은 나눗셈인 경우 순서를 생각해야 한다. 이런 경우를 대비해 스택에서 나중에 꺼내진 연산자로부터 먼저 꺼내진 연산자에 대한 연산을 실행한다 계산된 연산자는 다시 스택에 넣어준다. 후위 표기식이 다 끝났다면 스택에 남아있는 피연산자가 식의 답이다. 이전 포스..

1. 과제안내문 이번 과제는 후위 표기식 형식으로 수식을 입력하여 수식트리를 만들고, 이 트리를 중위로 순회하면서 중위 표기식을 출력하고, 수식을 계산한 결과를 출력한다. 수식트리에서 노드는 연산자 또는 피연산자 노드로 구성되는데, 내부 노드는 연산자 노드이고, 외부 노드는 피연산자 노드가 된다. 피연산자 노드는 노드의 데이터는 피연산자가 되고 자식 노드는 없다. 연산자 노드는 노드의 데이터는 연산자가 되고, 피연산자들은 연산자 노드의 자식 노드로 연결된다. 이진연산자는 두 자식을 가지지만, 단일연산자는 왼쪽 자식은 없고 오른쪽 자식만 가진다. 수식트리를 만드는 방식은 후위 표기식을 계산하는 방식과 비슷하다. 피연산자는 피연산자 노드를 만들어 그 노드를 스택에 Push 한다. 연산자는 연산자 노드를 만들..