중위 표기법에서 후위 표기법으로의 변환을 이해하기 전에 중위 표기법과 후위 표기법에 대해 별도로 알아야 합니다.

중위와 접미사는 표현식입니다. 표현식은 상수, 변수 및 기호로 구성됩니다. 기호는 연산자나 괄호일 수 있습니다. 이러한 모든 구성 요소는 규칙 집합을 사용하여 모든 표현식을 평가할 수 있도록 규칙 집합에 따라 배열되어야 합니다.

표현식의 예는 다음과 같습니다.

5 + 6

A - B

(피*5)

위의 모든 표현식은 공통 구조를 가지고 있습니다. 즉, 두 피연산자 사이에 연산자가 있습니다. 피연산자는 연산이 수행될 객체 또는 값입니다. 위 수식에서 5, 6은 피연산자이고 '+', '-', '*'는 연산자입니다.

중위 표기법이란 무엇입니까?

연산자가 피연산자 사이에 쓰여지면 다음과 같이 알려져 있습니다. 중위 표기법 . 피연산자는 항상 상수이거나 변수일 필요는 없습니다. 표현 자체가 될 수도 있습니다.

예를 들어,

(p + q) * (r + s)

위의 식에서 곱셈 연산자의 두 식은 모두 피연산자입니다. 즉, (p + q) , 그리고 (r + s) 피연산자입니다.

위의 표현식에는 세 개의 연산자가 있습니다. 첫 번째 플러스 연산자의 피연산자는 p와 q이고, 두 번째 플러스 연산자의 피연산자는 r과 s입니다. 수행하는 동안 표현식에 대한 연산을 수행하려면 결과를 평가하기 위해 몇 가지 규칙 세트를 따라야 합니다. 에서 위 식에서는 두 식, 즉 p+q와 r+s에 대해 덧셈 연산을 수행한 다음 곱셈 연산을 수행합니다.

숫자로 보는 알파벳

중위 표기법의 구문은 다음과 같습니다.

표현식에 연산자가 하나만 있는 경우 규칙을 적용할 필요가 없습니다. 예를 들어 5 + 2; 이 표현식에서는 두 피연산자(5와 2) 사이에 덧셈 연산을 수행할 수 있으며 연산 결과는 7이 됩니다.

표현식에 여러 연산자가 있는 경우 표현식을 평가하려면 몇 가지 규칙을 따라야 합니다.

표현식이 다음과 같은 경우:

4+6*2

더하기 연산자가 먼저 평가되면 표현식은 다음과 같습니다.

10 * 2 = 20

곱셈 연산자가 먼저 평가되면 표현식은 다음과 같습니다.

4 + 12 = 16

위의 문제는 연산자 우선순위 규칙을 따르면 해결될 수 있습니다. 대수식에서 연산자 우선 순위는 아래 표와 같습니다.

괄호가 첫 번째로 선호됩니다. 그런 다음 지수에 다음 우선권이 부여됩니다. 지수 연산자가 여러 개인 경우 연산은 오른쪽에서 왼쪽으로 적용됩니다.

예를 들어:

2^2^3 = 2^8

= 256

지수, 곱셈, 나눗셈 연산자가 평가됩니다. 표현식에 두 연산자가 모두 있으면 연산은 왼쪽에서 오른쪽으로 적용됩니다.

다음으로 선호되는 것은 덧셈과 뺄셈입니다. 표현식에서 두 연산자를 모두 사용할 수 있으면 왼쪽에서 오른쪽으로 이동합니다.

같은 우선순위를 갖는 연산자를 다음과 같이 부릅니다. 연산자 연관성 . 왼쪽에서 오른쪽으로 가면 왼쪽 결합이라고 합니다. 오른쪽에서 왼쪽으로 가면 오른쪽 결합이라고 합니다.

중위 표기법 문제

중위 표현식을 평가하려면 다음 사항을 알아야 합니다. 연산자 우선순위 규칙을 따르며, 연산자의 우선순위가 동일한 경우 다음을 따라야 합니다. 연관성 규칙. 중위 표기법에서는 작업이 수행되는 순서를 제어하기 위해 괄호를 사용하는 것이 매우 중요합니다. 괄호는 표현식의 가독성을 향상시킵니다. 중위 표현식은 표현식을 작성하는 가장 일반적인 방법이지만 중위 표현식을 모호함 없이 구문 분석하고 평가하는 것은 쉽지 않습니다. 그래서 수학자 및 논리학자들은 이 문제를 연구하여 접두사와 접미사라는 표현을 작성하는 두 가지 다른 방법을 발견했습니다. 두 표현식 모두 괄호가 필요하지 않으며 모호함 없이 구문 분석될 수 있습니다. 연산자 우선 순위 및 연관성 규칙이 필요하지 않습니다.

접미사 표현

후위 표현식은 피연산자 뒤에 연산자를 쓰는 표현식입니다. 예를 들어 중위 표기법(2+3)의 후위 표현은 23+로 쓸 수 있습니다.

후위 표현식과 관련된 몇 가지 주요 사항은 다음과 같습니다.

• 후위 표현에서는 왼쪽에서 오른쪽으로 쓴 순서대로 연산이 수행됩니다.
• 괄호가 필요하지 않습니다.
• 연산자 우선순위 규칙과 연관성 규칙을 적용할 필요가 없습니다.

후위 표현식을 평가하는 알고리즘

• 연산자를 만날 때까지 표현식을 왼쪽에서 오른쪽으로 스캔합니다.
• 작업 수행
• 표현식을 계산된 값으로 바꿉니다.
• 더 이상 연산자가 없을 때까지 1~3단계를 반복합니다.

위의 알고리즘을 예제를 통해 이해해보자.

중위 표현: 2 + 3 * 4

표현의 대부분 왼쪽부터 스캔을 시작하겠습니다. 곱셈 연산자는 왼쪽에서 오른쪽으로 스캔할 때 가장 먼저 나타나는 연산자입니다. 이제 표현식은 다음과 같습니다.

라텍스 부분 파생물

식 = 2 + 34*

= 2 + 12

이번에도 왼쪽에서 오른쪽으로 스캔해 보겠습니다. 표현식은 다음과 같습니다.

식 = 2 12 +

= 14

스택을 사용한 접미사 표현 평가.

• 왼쪽에서 오른쪽으로 표정을 스캔하세요.
• 표현식에서 피연산자를 만나면 스택에 피연산자를 푸시합니다.
• 표현식에서 연산자를 만나면 스택에서 해당 피연산자를 팝합니다.
• 표현식 스캔을 마치면 최종 값이 스택에 남아 있습니다.

스택을 사용한 후위 표현식의 평가를 이해해 봅시다.

예 1: 후위 표현: 2 3 4 * +

위 식의 결과는 14입니다.

예시 2: 후위 표현: 3 4 * 2 5 * +

위 식의 결과는 22입니다.

후위 표현을 평가하는 알고리즘

1. 문자 읽기
2. 문자가 숫자인 경우 문자를 int로 변환하고 정수를 스택에 푸시합니다.
3. 캐릭터가 오퍼레이터인 경우,
   • 두 개의 피연산자를 얻기 위해 스택에서 요소를 두 번 팝합니다.
   • 작업 수행
   • 결과를 스택에 푸시합니다.

중위를 후위로 변환

여기서는 중위 표현을 접두사 표현으로 변환하기 위해 스택 데이터 구조를 사용합니다. 연산자를 만날 때마다 우리는 연산자를 스택에 밀어 넣습니다. 피연산자를 만나면 피연산자를 표현식에 추가합니다.

중위 표현에서 후위 표현으로의 변환 규칙

1. 피연산자가 도착하면 인쇄하십시오.
2. 스택이 비어 있거나 상단에 왼쪽 괄호가 포함되어 있으면 들어오는 연산자를 스택에 푸시합니다.
3. 들어오는 기호가 '('이면 스택에 푸시합니다.
4. 들어오는 기호가 ')'이면 스택을 팝하고 왼쪽 괄호를 찾을 때까지 연산자를 인쇄합니다.
5. 들어오는 기호가 스택 상단보다 우선 순위가 높으면 해당 기호를 스택에 푸시합니다.
6. 들어오는 기호가 스택 상단보다 우선순위가 낮은 경우 스택 상단을 팝하고 인쇄합니다. 그런 다음 스택의 새 상단에 대해 들어오는 연산자를 테스트합니다.
7. 들어오는 연산자가 스택 상단과 동일한 우선 순위를 갖는 경우 연관성 규칙을 사용하십시오. 연관성이 왼쪽에서 오른쪽이면 스택의 상단을 팝하고 인쇄한 다음 들어오는 연산자를 푸시합니다. 연관성이 오른쪽에서 왼쪽이면 들어오는 연산자를 푸시합니다.
8. 표현식의 끝에서 스택의 모든 연산자를 팝하고 인쇄합니다.

예를 통해 이해해 봅시다.

중위 표현: K + L - M*N + (O^P) * W/U/V * T + Q

중위 표현식(K + L - M*N + (O^P) * W/U/V * T + Q)의 최종 후위 표현식은 KL+MN*-OP^W*U/V/T*+Q+입니다. .