표현 식 값 구하 기 (접미사 표현 식 - 접미사 표현 식 - 값 구하 기)

10493 단어 algorithm
표현 식 값 구 하 는 것 은 데이터 구조 인 스 택 의 전형 적 인 응용 에 속 합 니 다.접미사 표현 식 과 이 유 는 값 을 구 하 는 과정 에서 연산 자의 우선 순 위 를 고려 할 필요 가 없 기 때 문 입 니 다.(결합 성 은 여전히 고려 해 야 한다)
        그러나 일반적인 책 에 서 는 이원 조작 부 를 어떻게 처리 하 는 지, 그리고 결합 성 은 모두 왼쪽 에서 오른쪽으로 결합 된다.여기 서 의 실현 은 1 원 연산 자 를 처리 할 수 있 고 오른쪽 에서 왼쪽으로 결 합 된 멱 승 '^' 연산 자 를 처리 할 수 있 습 니 다.
기능 수요
        접두사 표현 식 을 지정 하여 이 표현 식 의 값 을 구하 십시오.        '가감 승제 + - * /, 취 여%, 멱 연산 ^, 일원 정 음호 + -, 괄호 (), 수의 과학적 표현법 기호 E e' 를 지원 해 야 합 니 다. 그 중 일원 조작 부호 '+ -' 도 포함 되 어 있 고 오른쪽 에서 왼쪽으로 결합 하 는 조작 부호 '^' 도 포함 되 어 있 습 니 다. 조작 수의 자릿수 가 여러 자리 일 수 있 음 을 주의 하 십시오.
분석 하 다.
        세 가지 측면 을 고려 해 야 한다. ① 우선 순위;② 결합 성;③ 몇 원 연산 자;
        우선 순위: 연산 자의 우선 순위 가 다 르 면 우선 순위 가 높 은 것 을 계산 합 니 다.
        결합 성: 연산 자의 우선 순위 가 같다 면 우선 순위 의 결합 성 을 계산 하여 값 을 구 하 는 순 서 를 결정 합 니 다.
        몇 원 연산 자: 1 원 과 2 원 연산 자 는 값 을 구 하 는 작업 에 참여 하 는 갯 수 를 결정 합 니 다.
처리 방법
        1. 숫자 0 을 이용 하여 일원 조작 을 이원 조작 으로 전환한다. 예 를 들 어 '- 3' 을 '0 - 3' 으로 전환한다.
        2. 연산 자 를 우선 순위 에 따라 분류 하여 각 연산 자의 우선 순 위 를 확인한다.
        3. 결합 성 이 다른 조작 자 는 수량 이 적 기 때문에 처리 할 때 단독으로 판단 합 니 다.
구체 적 절차
        1. 일치 하지 않 는 괄호 가 있 는 지 판단
        2. 접두사 식 전처리                2.1 처리 할 수 없 는 문자 가 있 는 지 판단 한다.                2.2 모든 빈 칸 제거 하기;                2.3 1 원 연산 자 '+' 와 '-' 를 처리 합 니 다.                        2.3.1 시작 위치 라면 시작 부분 에 '0' 을 추가 합 니 다.                        2.3.2 만약 에 '비 숫자 문자' (오른쪽 괄호 ') 를 제외 한 다음 에 1 원 연산 자 앞 에' (0 '을 삽입 한 다음 에' 완전한 숫자 '나' 괄호 뒤에 '오른쪽 괄호' 를 추가 합 니 다.
        3. 접두사 가 접두사 표현 식 으로 바 뀝 니 다.            접두사 표현 식 옮 겨 다 니 기:                3.1 조작 수 라면 모든 위 치 를 읽 고 접미사 식 대기 열 에 들 어 갑 니 다.                3.2 연산 자 라면 (+ – * / ^%)                        3.2.1 '조작 부호 창고' 가 비어 있 으 면 바로 창고 에 들어간다.                        3.2.2 현재 연산 자 우선 순위 > 스 택 상단 요소 우선 순위 가 있 으 면 스 택 에 들 어 갑 니 다.                        3.2.3 현재 연산 자 우선 순위                        3.2.4 현재 연산 자 우선 순위 = 스 택 상단 요소 우선 순위, 현재 요소 가 오른쪽 결합 성 이 라면 스 택 에 들 어 갑 니 다.그렇지 않 으 면 창고 꼭대기 원소 가 창고 에서 나온다.순환 실행.                3.3 왼쪽 괄호 '(') 이면 바로 창고 에 들어간다.                3.4 만약 에 오른쪽 괄호 ')', 만약 에 창고 가 비어 있 지 않 으 면 창고 꼭대기 요소 가 창고 에서 나 와 왼쪽 괄호 를 만 날 때 까지 '(');                3.5 반복 끝 에서 연산 자 스 택 의 요 소 를 순서대로 스 택 에서 나 와 접미사 식 대기 열 에 추가 합 니 다.        4. 계산 접미사 표현 식            접미사 식 대기 열 에서 요 소 를 순서대로 꺼 냅 니 다.                4.1 조작 수 라면 '결과 스 택' 에 눌 러 넣 습 니 다.                4.2 연산 자 라면 '결과 스 택' 에서 두 요 소 를 꺼 내 계산 합 니 다. (스 택 에서 요 소 를 찾 는 순서 와 조작 수의 순 서 는 반대 입 니 다.)                접미사 표현 식 이 끝 난 후에 '결과 스 택' 의 요 소 는 최종 결과 입 니 다.
구체 코드
/**
 *      -->     -->     
 *
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

/**
 *         
 *   :
 *      ch :       
 *    :
 *          ,  true;    false;
 */
bool is_operator(char ch) {
    set operator_set;
    operator_set.insert('+');
    operator_set.insert('-');
    operator_set.insert('*');
    operator_set.insert('/');
    operator_set.insert('%');
    operator_set.insert('^');
    return operator_set.find(ch) != operator_set.end();
}
/**
 *            
 */
int compare_priority(char a, char b) {
    map operator_priority;
    operator_priority.insert(make_pair('+', 1));
    operator_priority.insert(make_pair('-', 1));
    operator_priority.insert(make_pair('*', 2));
    operator_priority.insert(make_pair('/', 2));
    operator_priority.insert(make_pair('%', 2));
    operator_priority.insert(make_pair('^', 3));

    return operator_priority[a]-operator_priority[b];
}
/**
 *            
 */
bool is_bracket_valid(string infix) {
    stack bracket;
    for(int i=0; i valid_char_set;//       
    for(int i=0; i<=9; i++) {
        valid_char_set.insert(i+'0');
    }
    valid_char_set.insert('+');
    valid_char_set.insert('-');
    valid_char_set.insert('*');
    valid_char_set.insert('/');
    valid_char_set.insert('%');
    valid_char_set.insert('^');
    valid_char_set.insert('(');
    valid_char_set.insert(')');
    valid_char_set.insert('e');//'e' 'E'      
    valid_char_set.insert('E');
    valid_char_set.insert('.');//   

    for(int i=0; i=0 && !isdigit(result[i-1]) && result[i-1]!=')') { //  +-,         
            result.insert(i, "(0");
            int j = i+3;
            int bracket_count=0;//     ,     
            for(; j     
 */
queue infix_to_post(string infix) {
    queue postfix;//       
    stack operator_stack;//     ,         

    set valid_operand_set;//        
    for(int i=0; i<=9; i++) {
        valid_operand_set.insert(i+'0');
    }
    valid_operand_set.insert('.');
    valid_operand_set.insert('e');
    valid_operand_set.insert('E');

    for(int i=0; i        ,      、           “    ”。
            while(compare_priority(infix[i], top_stack)<=0) {
                //     ,              ,    '^'
                if(compare_priority(infix[i], top_stack)==0 && infix[i]=='^') {   //  '^'        ,      
                    break;
                }
                //     <=        ,             
                postfix.push(string(1, top_stack));
                operator_stack.pop();
                if(!operator_stack.empty()) {
                    top_stack = operator_stack.top();
                } else {
                    break;
                }

            }
            //        
            operator_stack.push(infix[i]);
        } else {//   
            string current_operator;
            int j=i;
            while(valid_operand_set.find(infix[j]) != valid_operand_set.end()) {
                current_operator += infix[j];
                ++j;
            }
            postfix.push(current_operator);
            i=j-1;//  for  ,      i++
        }
        
        //      
        cout< temp_queue = postfix;
        cout<0) {
            cout<(a)) % (static_cast(b));
    } else if(operand == "^") {
        result = pow(a, b);
    }
    return result;
}
//      ,    
double calculate_post(queue& post) {
    stack result_stack;
    while(!post.empty()) {
        string temp = post.front();
        post.pop();
        if(is_operator(temp[0])) { //    
            if(result_stack.size()<2) {
                cout< result_post = infix_to_post(result_infix);
    //       
    queue temp = result_post;
    cout<

실행 결과:
        :
10e2+3*4-5%2-2^-(4/2)+.2 + 2^1^3

       : 10e2+3*4-5%2-2^-(4/2)+.2 + 2^1^3

    

       10e2+3*4-5%2-2^-(4/2)+.2+2^1^3
     :10e2+3*4-5%2-2^(0-(4/2))+.2+2^1^3

  :  0    :  1
    :
       : 10e2

  :  4    :  +

  :  5    :  3
    : +
       : 10e2  3

  :  6    :  *
    : *
       : 10e2  3

  :  7    :  4
    : *
       : 10e2  3  4

  :  8    :  -
    : -
       : 10e2  3  4  *  +

  :  9    :  5
    : -
       : 10e2  3  4  *  +  5

  :  10    :  %
    : %
       : 10e2  3  4  *  +  5

  :  11    :  2
    : %
       : 10e2  3  4  *  +  5  2

  :  12    :  -
    : -
       : 10e2  3  4  *  +  5  2  %  -

  :  13    :  2
    : -
       : 10e2  3  4  *  +  5  2  %  -  2

  :  14    :  ^
    : ^
       : 10e2  3  4  *  +  5  2  %  -  2

  :  15    :  (
    : (
       : 10e2  3  4  *  +  5  2  %  -  2

  :  16    :  0
    : (
       : 10e2  3  4  *  +  5  2  %  -  2  0

  :  17    :  -
    : -
       : 10e2  3  4  *  +  5  2  %  -  2  0

  :  18    :  (
    : (
       : 10e2  3  4  *  +  5  2  %  -  2  0

  :  19    :  4
    : (
       : 10e2  3  4  *  +  5  2  %  -  2  0  4

  :  20    :  /
    : /
       : 10e2  3  4  *  +  5  2  %  -  2  0  4

  :  21    :  2
    : /
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2

  :  22    :  )
    : -
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /

  :  23    :  )
    : ^
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -

  :  24    :  +
    : +
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -

  :  25    :  .
    : +
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2

  :  27    :  +
    : +
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2  +

  :  28    :  2
    : +
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2  +  2

  :  29    :  ^
    : ^
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2  +  2

  :  30    :  1
    : ^
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2  +  2  1

  :  31    :  ^
    : ^
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2  +  2  1

  :  32    :  3
    : ^
       : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2  +  2  1  3
     : 10e2  3  4  *  +  5  2  %  -  2  0  4  2  /  -  ^  -  .2  +  2  1  3  ^  ^  +

    : 1012.95

Press any key to continue.

본문 링크:http://blog.csdn.net/daheiantian/archive/2011/03/19/6553713.aspx

좋은 웹페이지 즐겨찾기