学步园

一直以来都想像样的写个简单的利用栈结构来进行表达式求值的代码，以前转了一个用c写的表达式求值，有回复说有问题，其实是没有问题，只是不能处理超过2位数的非整形的表达式求值，现在我自己按照一样的算法写了一个多项表达式求值，支持+，-，*，/，^和括号的运算，暂时只支持双目运算，单目没测试，以后再有空再补上，支持小数和多位数（不支持大数运算）

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>

using namespace std;

enum eOperator {
    ADD=0,
    SUB,
    MUL,
    DIV,
    POW,
    LBRC,
    RBRC,
    MARK,
    NONE
};

vector<eOperator> s_operator;
vector<double> s_operand;

// + - * / ^ ( ) #
const int OPNUM=8;

char operator_ch[]="+=*/^()#";

//行表示即将进栈的操作符
//列表示栈顶操作符
char priority[OPNUM][OPNUM]= {

//   +    -   *   /   ^    (    )   #
    '<',  '<', '<', '<', '<', '>', '>', '>', // +
    '<',  '<', '<', '<', '<', '>', '>', '>', // -
    '>',  '>', '<', '<', '<', '>', '>', '>', // *
    '>',  '>', '<', '<', '<', '>', '>', '>', // /
    '>',  '>', '>', '>', '<', '>', '>', '>', // ^
    '>',  '>', '>', '>', '>', '>', 'E', '>', // (
    '<',  '<', '<', '<', '<', '=', '0', 'E', // )
    '<',  '<', '<', '<', '<', 'E', '<', '=', // #
};

void print_stack(eOperator current_op=NONE,double d=0);

double cal_exp(const double& op1, const double& op2, const eOperator & o) {
    switch(o)   {
    case ADD:        return op1 + op2;
    case SUB:        return op1 - op2;
    case MUL:        return op1 * op2;
    case DIV:        return op1/op2;
    case POW:        return pow(op1,op2);
    default:
        //cout<<"not supported"<<endl;
        break;
    }
}

//打印函数
void print_stack(eOperator current_op,double d) {
    if(current_op!=NONE)
        cout<<"Current Operator: "<<operator_ch[current_op] <<endl;
    else
        cout<<"Current Operand: "<<d <<endl;
    vector<eOperator>::iterator operator_it;
    vector<double>::iterator operand_it;
    cout<<"Operator Stack: ";
    for(operator_it=s_operator.begin();operator_it != s_operator.end();operator_it++)
        cout<<operator_ch[*operator_it] <<" ";
    cout<<endl;
    cout<<"Operand Stack: ";
    for(operand_it=s_operand.begin();operand_it != s_operand.end();operand_it++)
    {
        cout<<*operand_it<<" ";
    }
    cout<<endl;
    cout<<"------------------------"<<endl;

}

bool calc(const string& expr,double& out) {
    double result,op1,op2;
    eOperator t_op;

    int len=expr.length();
    double operand;
    int i=0;

    int point=-1;

    //压入#作为开始标记
    s_operator.push_back(MARK);

    while(s_operator.size()>0 && s_operator.back()!='#' ) {
        //get operand
        operand = 0;
        point = false;

        if(expr[i] == ' '||expr[i] == '\t'){ //过滤空字符
            i++;
            continue;
        }

        if((expr[i] >= '0' && expr[i] <= '9')||expr[i]=='.') { //如果是操作数，则开始取数据
            while((expr[i] >= '0' && expr[i] <= '9')||expr[i]=='.') {
                if(expr[i] == '.') //小数点
                    point = 1;
                else{
                    if(point  >= 0)
                        point ++; //计数小数位数
                     operand = expr[i]-'0' + operand  * 10; //整数部分
                }
                i++;
            }

            //操作数压栈
            if(point > 0)
                operand /= pow(10,point-1);
            print_stack(NONE,operand);
            s_operand.push_back(operand);

        } else if(expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/' ||
                  expr[i] == '^' || expr[i] == '(' || expr[i] == ')' || expr[i] == '#' ) {
            //处理操作符

            //get operation
            switch(expr[i]) {
            case '+':                t_op = ADD;                break;
            case '-':                t_op = SUB;                break;
            case '*':                t_op = MUL;                break;
            case '/':                t_op = DIV;                break;
            case '^':               t_op = POW;                 break;
            case '(':                t_op = LBRC;                break;
            case ')':                t_op = RBRC;                break;
            case '#':                t_op = MARK;                break;
            default:  break;              //cout<<"unsupported '"<<expr[i]<<"'"<<endl;
            }

            eOperator opTop = s_operator.back();
            switch(priority[t_op][opTop]){
                case '<':
                    print_stack(t_op);
                    op2=s_operand.back(); s_operand.pop_back();  //获取op2
                    op1=s_operand.back(); s_operand.pop_back(); //op1
                    s_operator.pop_back();
                    s_operand.push_back(cal_exp(op1,op2,opTop));
                    //此处还未处理当前的操作符号，所以无 i++

                    break;
                case '>':
                    print_stack(t_op);
                    s_operator.push_back(t_op);
                    i++; //继续下面的处理

                    break;
                case '=': //遇到右括号，弹出左括号
                    print_stack(t_op);
                    s_operator.pop_back();
                    if(t_op != MARK)
                        i++; //继续下面的处理

                    break;
                case 'E':
                    print_stack(t_op);
                    cout<<"[!!!]Error in expression: Exit!"<<endl;

                    return false;
                    break;
                default:
                    print_stack(t_op);
                    cout<<"[!!!]Unexpected Error: Exit!"<<endl;

                    return false;
            }

        } else {
            cout<<"Unsupported char, ignore it" << expr[i]<<endl;
            if(expr[i]!='#')
                i++;
        }

    }
    out = s_operand.back();
    return true;
}

int main() {
    double result;
    string in="2.34+2*(1+2.2*3+(2*5/2+4.56897/2.3+ 2.7))";

    if(calc(in+"#",result))
        cout<<in<<"="<<result<<endl;
    else
        cout<<in<<"="<<"N/A"<<endl;

    cout<<2.34+2*(1+2.2*3+(2*5/2+4.56897/2.3+ 2.7))<<endl;
    return 0;
}