📚 Notation(표현식)

📚 Notation(표현식)

• 연산자와 피연산자를 조합하여 값을 생성하는 식

---

🚀 중위 표기법(Infix Notation)

• 우리가 일반적으로 사용하는 연산식 형태
• A + B 같은 형태로 연산자가 피연산자 사이에 위치
• 우선수위와 괄호를 고려

✅ 예제

3 + 5
(2 * 3) + 4
a + b * c

✅ 특징

• 가독성이 높음(사람한테만)
• 연산자 우선순위를 고려해야함
• 괄호를 이용해 연산 순서를 명확히 표현해야 함

---

🚀 전위 표기법(Prefix Notation)

• 연산자가 피연산자 앞에 위치
• 괄호가 필요하지 않음

✅ 예제

+ 3 5   (→ 3 + 5)
* + 2 3 4  (→ (2 + 3) * 4)

✅ 특징

• 연산자의 위치가 고정되어 있어서 연산자 우선순위를 고려할 필요없음
• 괄호가 필요없음
• 컴퓨터가 연산하기에 적합한 구조

---

🚀 후위 표기법(Postfix Notation)

• 연산자가 피연산자 뒤에 위치
• 스택 을 이용하면 쉽게 계산 가능

✅ 예제

3 5 +   (→ 3 + 5)
2 3 + 4 *   (→ (2 + 3) * 4)

✅ 특징

• 연산자 우선순위를 고려할 필요가 없음
• 괄호 없이도 연산 순서가 명확함
• 스택을 이용해 쉽게 계산 가능

---

🔑 중위 → 후위 변환 (Shunting-yard 알고리즘)

✅ 변환 규칙

1. 숫자는 그대로 출력
2. 연산자는 스택에 저장 (우선순위 고려)
3. (는 스택에 push, )를 만나면 (가 나올 때까지 pop 후 출력
4. 모든 연산자 pop 후 출력

#include <iostream>
#include <stack>
#include <cctype>
using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string infixToPostfix(string infix) {
    stack<char> stk;
    string postfix = "";

    for (char ch : infix) {
        if (isdigit(ch)) {
            postfix += ch;
            postfix += ' ';
        } 
        else if (ch == '(') stk.push(ch);
        else if (ch == ')') {
            while (!stk.empty() && stk.top() != '(') {
                postfix += stk.top();
                postfix += ' ';
                stk.pop();
            }
            stk.pop();  // '(' 제거
        }
        else {  // 연산자
            while (!stk.empty() && precedence(stk.top()) >= precedence(ch)) {
                postfix += stk.top();
                postfix += ' ';
                stk.pop();
            }
            stk.push(ch);
        }
    }
    while (!stk.empty()) {
        postfix += stk.top();
        postfix += ' ';
        stk.pop();
    }
    return postfix;
}

int main() {
    string infix = "(2+3)*4";
    cout << infixToPostfix(infix);  // 출력: 2 3 + 4 *
}

• stl
• c