식 평가

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

표현 평가 문제에서 우리는 정수, 균형 괄호 및 이진 연산 (+,-, *, /)으로 구성 될 수있는 표현식을 나타내는 길이 n의 s. 식을 평가하십시오. 표현식은 접두사, 중위 또는 접미사 중 하나 일 수 있습니다. 표기법.

식 평가

표현식 평가에 대한 몇 가지 예를 참조하십시오.

입력 : s = "100 * (2 + 12)"

출력 : 1400

입력 : s = "10 + 2 * 6"

출력 : 22

식 평가를위한 알고리즘

이제 식 평가에 대한 문제 설명을 알았습니다. 그래서 우리는 시간을 낭비하지 않고 연산 식 평가 솔루션에 사용합니다.

  1. expression으로 구성된 길이 n의 문자열 s를 초기화합니다.
  2. 하나 생성 스택 값을 저장하고 다른 연산자를 저장합니다.
  3. 문자열을 가로 질러 현재 문자가 공백인지 확인하고 루프를 계속합니다. 그렇지 않으면 여는 괄호 인 경우 연산자 스택에 밀어 넣습니다.
  4. 그렇지 않으면 현재 문자가 숫자 인 경우. 정수 val을 0으로 초기화합니다. 현재 문자가 숫자 인 동안 현재 위치 + 1에서 문자열 끝까지 순회하고 val * 10 + 현재 숫자로 업데이트합니다. 가치 더미에 밀어 넣으십시오.
  5. 그렇지 않으면 닫는 괄호이면 연산자 스택이 비어 있지 않고 현재 문자가 여는 괄호가 아닌 동안 트래버스합니다.
  6. 값 스택에서 상위 2 개 숫자와 연산자 스택에서 연산자를 팝합니다. 산술 연산을 수행하고 결과를 값 스택으로 푸시합니다.
  7. 연산자 스택이 비어 있지 않은 동안 값 스택에서 상위 2 자리 숫자와 연산자 스택에서 연산자를 팝합니다. 산술 연산을 수행하고 결과를 값 스택으로 푸시합니다.
  8. 값 스택의 맨 위를 반환합니다.

식 평가를위한 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("100 * ( 2 + 12 )") << endl; 
    
    return 0; 
}
1400

표현식 평가를위한 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("100 * ( 2 + 12 )")); 
        
    } 
}
1400

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 평가할 표현식의 길이입니다.

공간 복잡성 : n 문자를 저장하는 데 필요한 공간이므로 O (n).

참조

Translate »