산술 식 평가

난이도 중급
자주 묻는 질문 아마존 신탁
수학 스택조회수 44

다음 세 가지 표기법으로 산술 표현식을 작성합니다.

접두사 표기법

이 표기법에서 피연산자는 연산자 뒤에 기록됩니다. 폴란드 표기법이라고도합니다.

예 : + AB는 접두사 표현식입니다.

중위 표기법

이 표기법에서 연산자는 피연산자 사이에 기록됩니다. 우리가 일반적으로 표현을 쓰는 것과 비슷합니다.

예를 들어 : A + B는 중위 식입니다.

후위 표기법

이 표기법에서 피연산자는 연산자 앞에 기록됩니다. 역 폴란드어 표기법이라고도합니다.

예 : AB +는 접미사 표현식입니다.

이러한 식의 평가를 통해 (a + b) * c와 a + (b * c)의 결과 차이를 확인할 수 있습니다.

산술 식 평가 규칙-

  • 먼저 괄호를 풉니 다. 즉, 먼저 괄호 안의 하위 표현식을 해결하십시오. 중첩 된 괄호의 경우 가장 안쪽 괄호부터 시작합니다.
  • 식 또는 하위 식에 괄호가 포함되지 않은 경우 연산자의 우선 순위에 따라식이 해결됩니다. 5 개의 이항 연산자의 우선 순위 –

산술 식 평가

예를 들어 –

식 = 4/2-[(5 * 3) + (abs (-7))]

위의 식을 푸는 단계 –

  1. 먼저 내부 괄호, 즉 (5 * 3)과 (abs (-7))을 풀 것입니다.
  2. 그 후, 우리는 바깥 괄호, 즉 안쪽 괄호의 결과의 추가를 해결합니다.
  3. 그 후, 빼기 연산자 위의 나누기 연산자의 우선 순위에 따라 4/2를 풀 것입니다.
  4. 마지막으로 4/2의 결과와 위의 외부 괄호를 뺍니다.

산술 식 평가

따라서 결과 = -20

입력 : 4/2-[(5*3)+(abs(-7))]

출력 : -20

입력 : 100 * (2 + 12)

출력 : 1400

산술 식 평가를위한 알고리즘

  1. 초기화 값과 연산자를 저장하기위한 표현식과 두 개의 스택으로 구성됩니다.
  2. 0부터 문자열 크기까지 반복 – 1. 현재 인덱스의 문자가 공백과 같은지 확인하고 다음 반복을 시작합니다. 현재 인덱스의 문자가 '('와 같으면 연산자 스택에 삽입합니다.
  3. 현재 색인의 문자가 숫자 인 경우. 숫자 옆에 숫자가 있는지 확인하고 전체 숫자를 선택하고 한자리 숫자이면 숫자를 선택합니다. 값 스택에 숫자 / 숫자를 삽입하십시오.
  4. 그렇지 않으면 현재 인덱스의 문자가 ')'이면 연산자 스택의 크기가 XNUMX이 아니고 현재 인덱스의 문자가 '('와 같지 않은 동안 반복합니다.
  5. 그 후 값의 스택 맨 위에서 2 개 요소를 제거하고 연산자에서 1 개 요소를 제거합니다. 스택.
  6. 팝된 두 자리 / 숫자에 산술 연산을 적용합니다. 값 스택에 답을 삽입하십시오.
  7. 마찬가지로 연산자 스택의 크기가 2이 아니지만 값 스택의 맨 위에있는 요소 XNUMX 개와 연산자 스택에서 연산자를 제거합니다.
  8. 팝된 두 자리 / 숫자에 산술 연산을 적용합니다. 값 스택에 답을 삽입하십시오.
  9. 값 스택의 맨 위에있는 요소를 반환합니다.

산술 식 평가를위한 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
int precedence(char op){ 
    if(op == '+'||op == '-') 
        return 1; 
    if(op == '*'||op == '/') 
        return 2; 
    return 0; 
} 
  
int applyOp(int a, int b, char op){ 
    switch(op){ 
        case '+': 
            return a + b; 
        case '-': 
            return a - b; 
        case '*': 
            return a * b; 
        case '/': 
            return a / b; 
    } 
} 
  
int evaluate(string tokens){ 
    int i; 
      
    stack <int> values; 
      
    stack <char> ops; 
      
    for(i = 0; i < tokens.length(); i++){ 
          
        if(tokens[i] == ' ') 
            continue; 
          
        else if(tokens[i] == '('){ 
            ops.push(tokens[i]); 
        } 
          
        else if(isdigit(tokens[i])){ 
            int val = 0; 
              
            while(i < tokens.length() && isdigit(tokens[i])){ 
                val = (val*10) + (tokens[i]-'0'); 
                i++; 
            } 
              
            values.push(val); 
        } 
          
        else if(tokens[i] == ')'){ 
            
            while(!ops.empty() && ops.top() != '('){ 
                int val2 = values.top(); 
                values.pop(); 
                  
                int val1 = values.top(); 
                values.pop(); 
                  
                char op = ops.top(); 
                ops.pop(); 
                  
                values.push(applyOp(val1, val2, op)); 
            } 
              
            if(!ops.empty()) 
               ops.pop(); 
        } 
          
        else{ 
            while(!ops.empty() && precedence(ops.top()) >= precedence(tokens[i])){ 
                int val2 = values.top(); 
                values.pop(); 
                  
                int val1 = values.top(); 
                values.pop(); 
                  
                char op = ops.top(); 
                ops.pop(); 
                  
                values.push(applyOp(val1, val2, op)); 
            } 
              
            ops.push(tokens[i]); 
        } 
    } 
      
    while(!ops.empty()){ 
        int val2 = values.top(); 
        values.pop(); 
                  
        int val1 = values.top(); 
        values.pop(); 
                  
        char op = ops.top(); 
        ops.pop(); 
                  
        values.push(applyOp(val1, val2, op)); 
    } 
      
    return values.top(); 
} 
  
int main(){ 
    
    cout << evaluate("4 / 2 - ( ( 5 * 3 ) + 7 )") << endl; 
    
    return 0; 
}
-20

산술 식 평가를위한 Java 프로그램

import java.util.Stack; 
  
class EvaluateString{
    
    public static int evaluate(String expression){
        
        char[] tokens = expression.toCharArray(); 
  
        Stack<Integer> values = new Stack<Integer>(); 
  
        Stack<Character> ops = new Stack<Character>(); 
  
        for (int i = 0; i < tokens.length; i++){ 
             
            if(tokens[i] == ' ') 
                continue; 
  
            if(tokens[i] >= '0' && tokens[i] <= '9'){ 
                StringBuffer sbuf = new StringBuffer(); 
                
                while(i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9'){
                    sbuf.append(tokens[i++]); 
                }
                
                values.push(Integer.parseInt(sbuf.toString())); 
            } 
  
            else if(tokens[i] == '(') 
                ops.push(tokens[i]); 
  
            else if(tokens[i] == ')'){ 
                while (ops.peek() != '('){ 
                  values.push(applyOp(ops.pop(), values.pop(), values.pop())); 
                }  
                ops.pop(); 
            } 
  
            else if(tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/'){ 
                
                while (!ops.empty() && hasPrecedence(tokens[i], ops.peek())){ 
                  values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                }  
  
                ops.push(tokens[i]); 
            } 
        } 
  
        while(!ops.empty()){ 
            values.push(applyOp(ops.pop(), values.pop(), values.pop())); 
        }    
  
        return values.pop(); 
    } 
  
    public static boolean hasPrecedence(char op1, char op2){ 
        if (op2 == '(' || op2 == ')') 
            return false; 
        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) 
            return false; 
        else
            return true; 
    } 
  
    public static int applyOp(char op, int b, int a){ 
        switch (op){ 
            case '+': 
                return a + b; 
            case '-': 
                return a - b; 
            case '*': 
                return a * b; 
            case '/': 
                if (b == 0) 
                    throw new
                    UnsupportedOperationException("Cannot divide by zero"); 
                return a / b; 
        } 
        return 0; 
    } 
  
    public static void main(String[] args){
        
        System.out.println(EvaluateString.evaluate("4 / 2 - ( ( 5 * 3 ) + 7 )")); 
        
    } 
}
-20

산술 식 평가를위한 복잡성 분석

시간 복잡성 : O (n) 여기서 n은 주어진 문자열 s의 크기입니다.

공간 복잡성 : O (n) n 요소에 스택 공간을 사용했기 때문입니다.

참조

Translate »