중위 표기법이란 무엇입니까?
중위 표기법은 표현식이 일반적인 또는 일반 형식으로 작성된 표기법입니다. 연산자가 피연산자 사이에 위치하는 표기법입니다. 중위 표기법의 예로는 A+B, A*B, A/B 등이 있습니다.
위의 예에서 볼 수 있듯이 모든 연산자는 피연산자 사이에 존재하므로 중위 표기법입니다. 따라서 중위 표기법의 구문은 다음과 같이 작성할 수 있습니다.
중위 표현 구문 분석
표현식을 구문 분석하려면 다음 두 가지를 처리해야 합니다. 연산자 우선순위 그리고 연관성 . 연산자 우선 순위는 다른 연산자보다 특정 연산자의 우선 순위를 의미합니다. 예를 들어:
A + B * C → A + (B * C)
곱셈 연산자는 더하기 연산자보다 우선순위가 높으므로 B * C 표현식이 먼저 평가됩니다. B * C의 곱셈 결과가 A에 추가됩니다.
우선순위
| 연산자 | 기호 |
|---|---|
| 괄호 | { }, ( ), [ ] |
| 지수 표기법 | ^ |
| 곱셈과 나눗셈 | *, / |
| 덧셈과 뺄셈 | +, - |
연관성은 동일한 우선순위를 갖는 연산자가 표현식에 존재하는 경우를 의미합니다. 예를 들어, A + B - C와 같은 표현식에서 '+' 및 '-' 연산자는 동일한 우선순위를 가지므로 연관성의 도움으로 평가됩니다. '+'와 '-'는 모두 왼쪽 결합이므로 (A + B) - C로 평가됩니다.
연관성 순서
| 연산자 | 연관성 |
|---|---|
| ^ | 오른쪽에서 왼쪽으로 |
| *, / | 왼쪽에서 오른쪽으로 |
| +, - | 왼쪽에서 오른쪽으로 |
예를 통해 연관성을 이해해 봅시다.
1 + 2*3 + 30/5
위 식에서 *와 /의 우선순위가 동일하므로 결합성 규칙을 적용하겠습니다. 위 표에서 볼 수 있듯이 * 및 / 연산자는 왼쪽에서 오른쪽으로 연관성이 있으므로 가장 왼쪽 연산자부터 스캔합니다. 먼저 오는 연산자가 먼저 평가됩니다. * 연산자는 / 연산자 앞에 나타나며 곱셈이 먼저 수행됩니다.
1+ (2*3) + (30/5)
1+6+6 = 13
접두사 표기법이란 무엇입니까?
접두사 표기법은 표현의 또 다른 형태이지만 우선 순위 및 연관성과 같은 다른 정보가 필요하지 않은 반면, 중위 표기법에는 우선 순위 및 연관성에 대한 정보가 필요합니다. 그것은 또한로 알려져 있습니다 폴란드어 표기법 . 접두사 표기법에서는 연산자가 피연산자 앞에 옵니다. 접두사 표기법의 구문은 다음과 같습니다.
예를 들어, 중위 표현식이 5+1이면 이 중위 표현식에 해당하는 접두사 표현식은 +51입니다.
중위 표현이 다음과 같은 경우:
a * b + c
↓
*ab+c
↓
+*abc(접두사 표현)
또 다른 예를 고려해보세요:
A + B * C
첫 스캔: 위의 표현식에서 곱셈 연산자는 더하기 연산자보다 우선순위가 높습니다. B*C의 접두사 표기법은 (*BC)입니다.
개발자 모드를 닫는 방법
A + *기원전
두 번째 스캔: 두 번째 스캔에서 접두사는 다음과 같습니다.
+A *기원전
위의 표현식에서는 중위어를 접두어 표현식으로 변환하기 위해 두 번의 스캔을 사용합니다. 표현식이 복잡하면 더 많은 스캔이 필요합니다. 단 한 번의 스캔만 필요하고 원하는 결과를 제공하는 방법을 사용해야 합니다. 한 번의 스캔을 통해 원하는 출력을 얻으면 알고리즘이 효율적일 것입니다. 이는 스택을 사용해야만 가능합니다.
스택을 사용하여 중위를 접두어로 변환
K + L - M * N + (O^P) * W/U/V * T + Q
표현식을 중위에서 접두어로 변환하려면 먼저 표현식을 반대로 바꿔야 합니다.
역방향 표현식은 다음과 같습니다.
Q + T * V/U/W * ) P^O(+ N*M - L + K
접두사 식을 얻기 위해 입력 식, 스택 및 접두사 식의 세 가지 열로 구성된 테이블을 만들었습니다. 어떤 기호를 만나면 간단히 접두사 표현식에 추가하면 됩니다. 연산자를 만나면 이를 스택에 푸시합니다.
| 입력식 | 스택 | 접두사 표현 |
|---|---|---|
| 큐 | 큐 | |
| + | + | 큐 |
| 티 | + | QT |
| * | +* | QT |
| 안에 | +* | QTV |
| / | +*/ | QTV |
| 안에 | +*/ | QTVU |
| / | +*// | QTVU |
| 안에 | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| 피 | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| 영형 | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| 중 | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| 엘 | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| 케이 | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
위의 표현식, 즉 QTVUWPO^*//*NM*LK+-++는 최종 표현식이 아닙니다. 접두사 표현식을 얻으려면 이 표현식을 뒤집어야 합니다.
중위를 접두사 표현으로 변환하는 규칙:
- 먼저, 문제에 주어진 중위 표현을 뒤집어 보세요.
- 왼쪽에서 오른쪽으로 표정을 스캔하세요.
- 피연산자가 도착할 때마다 인쇄하십시오.
- 연산자가 도착했는데 스택이 비어 있는 것으로 확인되면 간단히 연산자를 스택에 밀어넣으면 됩니다.
- 들어오는 연산자가 스택의 TOP보다 우선 순위가 높으면 들어오는 연산자를 스택에 푸시합니다.
- 들어오는 연산자가 스택의 TOP과 동일한 우선 순위를 갖는 경우 들어오는 연산자를 스택에 푸시합니다.
- 들어오는 연산자가 스택의 TOP보다 우선순위가 낮은 경우 스택의 맨 위를 팝하고 인쇄합니다. 스택 상단에 대해 들어오는 연산자를 다시 테스트하고 우선 순위가 낮거나 동일한 우선 순위의 연산자를 찾을 때까지 스택에서 연산자를 팝합니다.
- 들어오는 연산자가 스택 상단과 동일한 우선순위를 갖고 들어오는 연산자가 ^인 경우 조건이 true가 될 때까지 스택 상단을 팝합니다. 조건이 true가 아닌 경우 ^ 연산자를 누릅니다.
- 표현식의 끝에 도달하면 스택 상단의 모든 연산자를 팝하고 인쇄합니다.
- 연산자가 ')'이면 스택에 푸시합니다.
- 연산자가 '('인 경우 스택에서 여는 괄호를 찾을 때까지 스택에서 모든 연산자를 팝합니다.
- 스택의 맨 위가 ')'이면 스택에 연산자를 푸시합니다.
- 마지막에는 출력을 반대로 합니다.
접두사에서 접두사로의 변환 의사코드
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>