Infix to Postfix (C#, JAVA)

Infix to Postfix

infix to postfix 수행 과정

1. 수식에서 첫번째 항목을 빼냅니다.

2. 수식의 빼낸 항목이 피연산자라면 그대로 출력측으로 빼냅니다

3. 수식의 빼낸 항목이 연산자라면 스택의 최상위 원소와 비교합니다.

4. 빼낸 연산자의 우선순위가 스택의 최상위에 있는 원소보다 높으면 그대로 스택에 넣습니다.

5. 그렇지 않다면 스택의 최상위 원소를 출력측으로 뺴내고 빼낸 연산자를 스택에 넣습니다.

6. 단, 여는 괄호'('가 나오면 닫는괄호')'가 나올 때까지 스택에 남아있게 되며, 닫는괄호')'가 나타나면 그때까지 여는괄호'('보다 상위에 있는 모든 연산자를 출력측으로 빼냅니다.

We use a stack

• When an operand is read, output it

• When an operator is read

– Pop until the top of the stack has an element of lower 

precedence

– Then push it

• When ) is found, pop until we find the matching (

• ( has the lowest precedence when in the stack

• but has the highest precedence when in the input

• When we reach the end of input, pop until the stack is 

empty

설계 주요 사항

- stack 을 이용하여 자료구조를 표현하되 stack 은 static array(정적배열)을 사용함

- java는 객체지향 관점으로 stack 클래스와 infix2post 클래스를 생성하여 수행하였음. 

- c#은 절차지향 관점으로 main 함수 내에 필요한 stack 과 infix2post 과정을 함수로 작성하였음. 

java - 

infix2postfix_java.zip

c# - 

infix2postfix_cshap.zip

reference : 

1. http://makebob.tistory.com/18

2. http://cs.nyu.edu/courses/Fall12/CSCI-GA.1133-002/notes/InfixToPostfixExamples.pdf