经典算法问题-表达式求值

Oct 3, 2011 • {"display_name"=>"pensz", "login"=>"pensz", "email"=>"email", "url"=>""}

上次和同事聊到了验证码中有表达式求值的问题，说起来应该是比较简单了，也是数据结构上经典的算法问题。可是自己写一写才会发现，做对一件看似简单的事情不是那么容易。

本来自己弄了一个c的stack，但是c没有模板，想不到怎么支持不同的类型，只好换用c++了。

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

#include <stack>
#include <iostream>

using namespace std;


/**
 * 比较运算符之间的优先级
 */
static short int Precede(char c1, char c2) {
    if (c1 == c2) {
        if (c1 == '#') {
            return 0;
        } else if(c1 == '(') {
            return -1;
        } else {
            return 1;
        }
    }
    
    switch (c1) {
        case '+':
        case '-':
        
        if (c2 == '*' || c2 == '/' || c2 == '(') {
            return -1;
        } else {
            return 1;
        }
        break;
        
        case '*':
        case '/':
        if (c2 == '(') {
            return -1;
        } else {
            return 1;
        }
        break;
        
        case '(':
        if (c2 == ')') {
            return 0;
        } else {
            return -1;
        }
        break;
        
        case ')':
        return 1;
        break;
        
        case '#':
        return -1;
    }
}

/**
 * 对加减乘除进行求值
 */
static float Operate(float a, char theta, float b) {
    switch (theta) {
        case '+':
        return a+b;
        break;
        
        case '-':
        return a-b;
        break;
        
        case '*':
        return a*b;
        break;
        
        case '/':
        return a/b;
        break;
    }
    
    printf("bad operator");
    return 0;
}


int main() {
    
    stack<char> optr;
    stack<float> opnd;
    
    optr.push('#');
    
    char theta, tmp[20], *tmppoint, basechar[20];
    tmppoint = basechar;
    float a, b;
    
    char c = getchar();
    
    while (c!='#' || optr.top() != '#') {
        if (isdigit(c)) {
            *(tmppoint++) = c;
            c = getchar();
        } else {
            
            if (tmppoint > basechar) {
                *tmppoint = '
';
                opnd.push(atof(basechar));
                printf ("push number %s\n", basechar);
                tmppoint = basechar;
            }
            
            if (c != '+' && c != '-' && c != '*' && c != '/' && c != '(' && c != ')' && c != '#' ) {
                c = getchar();
                continue;
            }
            
            short int precede = Precede(optr.top(), c);
            switch (precede) {
                case -1:
                optr.push(c);
                printf("pushed operator %c \n", c);
                c = getchar();
                break;
                
                case 0:
                optr.pop();
                c = getchar();
                break;
                
                case 1:
                theta = optr.top();
                optr.pop() ;
                
                if (opnd.empty()) {
                    printf("opnd is empty\n");
                }
                b = opnd.top();
                opnd.pop();
                
                a = opnd.top();
                opnd.pop();
                
                cout << " cal a=" << (float)a << " theta=" << theta << " b=" << (float)b << endl;

                opnd.push(Operate(a, theta, b));
                break;
            }
        }
    }
    
    /* 最后的结果 */
    printf("%f\n", opnd.top());
    printf("%c\n", optr.top());
    
    return 0;
}