창고 의 응용 - 표현 식 값 구하 기

창고 의 응용 - 표현 식 값 구하 기
제목 설명
표현 식 을 지정 합 니 다. 그 중에서 연산 자 는 +, -, *, / (가감 승 정제) 만 포함 하고 괄호 를 포함 할 수 있 습 니 다. 표현 식 의 최종 값 을 구 하 십시오.주의:
4. 567917. 데 이 터 는 주어진 표현 식 이 합 법 적 임 을 보증 합 니 다
4. 567917. 문제 보증 기호 - 마이너스 로 만 나타 나 고 마이너스 로 나타 나 지 않 습 니 다. 예 를 들 어 - 1 + 2, (2 + 2) * (- (1 + 1) + 2) 와 같은 표현 식 은 나타 나 지 않 습 니 다
4. 567917. 제목 보증 표현 식 의 모든 숫자 는 정수 입 니 다
4. 567917. 문제 보증 표현 식 은 중간 계산 과정 과 결과 에서 모두 2 ^ 31 - 1 을 초과 하지 않 습 니 다
4. 567917. 문제 중의 정 제 는 0 을 가리 키 는 것 이다. 즉, 0 이상 의 결과 에 대해 아래로 정 리 를 하 는 것 이다. 예 를 들 어 5 / 3 = 1, 0 이하 의 결과 에 대해 위로 정 리 를 하 는 것 이다. 예 를 들 어 5 / (1 - 4) = - 1
4. 567917. C + + 와 자바 의 정 제 는 기본적으로 0 으로 정 리 됩 니 다.Python 의 정리 / / 기본 값 은 아래로 추출 되 기 때문에 Python 의 eval () 함수 에서 의 정리 도 아래로 추출 되 어 이 문제 에서 직접 사용 할 수 없습니다.원본 링크:https://www.acwing.com/problem/content/description/3305/
문제 풀이 의 사고 방향.
우선 기호의 우선 순위 ")" > "/" = "*" > "+" = "-" > "(" 이후 우선 순위 비교 가 있 기 때문에 우선 순위 의 높 고 낮 음 을 hash 표 로 저장 합 니 다.

unordered_map<char, int> pr{
     {
     '+', 1}, {
     '-', 1}, {
     '*', 2}, {
     '/', 2}};

명확 한 사고방식: STEP 1: 산술 표현 식 을 접미사 표현 식 으로 변환 합 니 다. STEP 2: 그리고 이 접미사 표현 식 에 값 을 구 합 니 다.
전체 코드

#include 
#include 
#include 
#include 
#include 

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
     
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
     
    unordered_map<char, int> pr{
     {
     '+', 1}, {
     '-', 1}, {
     '*', 2}, {
     '/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
     
        auto c = str[i];
        if (isdigit(c))
        {
     
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            //                 12     '1' '2'
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        //         
        else if (c == ')')
        {
     
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
     
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}