Evaluation of Expressions(1)

Expression: 연산문

특징: 결괏값 있음
arithmetic value(산술적인 결괏값): number
logical value(논리값): True(1) or False(0)

operand: 피연산자

operator: 연산자

parentheses: 괄호

Expression은 위의 세 가지로 구성되어 있다.

((rear+1==front)||((rear==MAX_QUEUE_SIZE-1)&&!front))

(rear+1==front) -> Expression

• rear, 1, front, ... -> Operarnd
• +, -, ... -> Arithmetic Value 산출하는 Operator
• ==, ||, &&, ... -> Logical Value 산출하는 Operator

operator 사이엔 precedence(우선순위) 존재함.

Postfix Expression의 특징:

1. 괄호 없이 operator의 우선순위 판단할 수 있음.
2. single left-to-right scan으로 evaluation 가능.
3. 먼저 나온 operator 먼저 계산.
4. operator의 직전 2개의 값이 operand.
5. operand의 순서는 infix와 같다.
   
   
   

Infix notation에서 Postfix notation으로의 변경법:

예) 5 + 3 * 2

1. precedence rule에 따라 괄호 적용
   (5 + (3 * 2))
2. 해당 operator에 대응하는 right parentheses ')' 왼쪽에 operator 이동
   (5 (3 2 *)+)
3. parentheses 모두 제거
   532*+
   

Evaluating Postfix Expressions: analysis

• n: number of tokens in the expression
• extracting tokens and outputting them: θ(n)
• in two while loop, the number of tokens that get stacked and unstacked is linear in n: θ(n)

total time complexity: θ(n)