算数表达式求值C++实现

  • Post author:
  • Post category:其他



为了简化问题,关注算法,本文的讨论基于以下三点:


1. 只考虑 + – * / ( ) 这几个基本运算符,且是二元操作


2. 运算数只考虑 0-9,这10个简单的数,方便从string中取出来


3. 输入的表达式没有语法错误



【背景知识】


中缀表示法(Infix expression):操作符位于两个操作数中间,算术表达式的常规表示法。只用于二元操作符的情况,而且需要用括号和优先规则排除多义性。(A+B)*C-D/(E+F)


前缀表示法(Prefix expression):也叫波兰表示法,操作符写在操作数的前面。这种方法常用于编译器设计方面。-*+ABC/D+EF


后缀表示法(Postfix expression),逆波兰表示法,操作符位于操作数后面。这种方法使表达式求值很方便。AB+C*DEF+/-



前、后缀表示法的三个特征:


1. 操作数的顺序与等价的中缀表示法中操作数的顺序一致


2. 不需要括号


3. 操作符的优先级不相关



用二叉树来表示更直观,前、中、后缀表示法分别对应前序、中序、后序遍历得到的结果。






【算符优先法】


输入中缀表达式,直接求值。首先了解四则运算的规则:


(1) 先乘除,后加减


(2) 从左到右


(3) 先括号内,后括号外



根据以上3条规则,在运算的每一步,任意两个相继出现的算符optr1和optr2之间的优先关系有3种:


>:optr1的优先权高于optr2


=:optr1的优先权等于optr2


<:optr1的优先权低于optr2


下表定义了算符之间的优先级。竖:optr1,横:optr2。



+




*


/


(


)


#


+


>


>


<


<


<


>


>




>


>


<


<


<


>


>


*


>


>


>


>


<


>


>


/


>


>


>


>


<


>


>


(


<


<


<


<


<


=



)


>


>


>


>



>


>


#


<


<


<


<


<



=



在表达式的两头,分别加个#符号,当##配对时,代表求值完成。


由规则(1),+ – 比* / 的优先权低;由规则(2),当optr1=optr2时,令optr1 > optr2;由规则(3),optr1为+ – * / 时的优先级低于 ( 高于 ) ,当optr1为 ( 时,优先级最低,optr1为 ) 时,优先级最高。



算法实现:使用两个栈,分别存放操作符和操作数。


1)置操作数栈为空,起始符#入运算符栈。


2)依次读入表达式中的每个字符,如是操作数,入操作数栈;如是运算符,和运算符栈顶符号比较优先权。直到表达式求值完毕,即##配对。




bool IsOperator(char ch)  
{  
    if (ch == '+' || ch == '-' ||  
        ch == '*' || ch == '/' ||  
        ch == '(' || ch == ')' || ch == '#')  
        return true;  
    else  
        return false;  
          
}  
//运算符的优先关系  
                         //'+', '-', '*', '/', '(', ')', '#'   
char OprRelation[7][7] = {{'>', '>', '<', '<', '<', '>', '>'}, //'+'  
                          {'>', '>', '<', '<', '<', '>', '>'}, //'-'  
                          {'>', '>', '>', '>', '<', '>', '>'}, //'*'  
                          {'>', '>', '>', '>', '<', '>', '>'}, //'/'  
                          {'<', '<', '<', '<', '<', '=', ' '}, //'('  
                          {'>', '>', '>', '>', ' ', '>', '>'}, //')'  
                          {'<', '<', '<', '<', '<', ' ', '='}};//'#'  
  
int ConvertToIndex(char opr)  
{  
    int index;  
  
    switch (opr)  
    {  
    case '+':  
        index = 0;  
        break;  
    case '-':  
        index = 1;  
        break;  
    case '*':  
        index = 2;  
        break;  
    case '/':  
        index = 3;  
        break;  
    case '(':  
        index = 4;  
        break;  
    case ')':  
        index = 5;  
        break;  
    case '#':  
        index = 6;  
        break;  
    }  
  
    return index;  
}  
  
char Precede(char opr1, char opr2)  
{  
    int index1 = ConvertToIndex(opr1);  
    int index2 = ConvertToIndex(opr2);  
  
    return OprRelation[index1][index2];  
}  
  
int Operate(int opnd1, char op, int opnd2)  
{  
    int ret;  
  
    switch(op)  
    {  
    case '+':  
        ret = opnd1 + opnd2;  
        break;  
    case '-':  
        ret = opnd1 - opnd2;  
        break;  
    case '*':  
        ret = opnd1 * opnd2;  
        break;  
    case '/':  
        ret = opnd1 / opnd2;  
        break;  
    }  
  
    return ret;  
}  
  
//算符优先算法  
int CaculateExpression(string exp)  
{  
    stack<char> optr; //只处理+ - # / ()运算  
    stack<int> opnd;  //只处理0-9的整数运算  
    char ch;  
    int i = 0;  
      
    exp += "#";  
    optr.push('#');  
      
    ch = exp[i++];  
      
    //如果##配对,表达式求值完成  
    while (ch != '#' || optr.top() != '#')  
    {  
        if (!IsOperator(ch))  
        {  
            //操作数入栈  
            opnd.push(ch - '0');  
            ch = exp[i++];  
        }  
        else  
        {  
            //比较栈顶操作符和新取得的操作符的优先关系  
            switch (Precede(optr.top(), ch))  
            {  
            case '<'://栈顶优先权低  
                optr.push(ch);  
                ch = exp[i++];  
                break;  
            case '='://括号配对,栈顶括号弹出  
                optr.pop();  
                ch = exp[i++];  
                break;  
            case '>'://栈顶优先权高,先弹出,计算,结果操作数入栈  
                char op = optr.top();  
                optr.pop();  
                int num2 = opnd.top();//第二个操作数在前  
                opnd.pop();  
                int num1 = opnd.top();  
                opnd.pop();  
                  
                int ret = Operate(num1, op, num2);  
                  
                opnd.push(ret);  
                break;  
            }  
        }  
    }//end of while  
  
    //操作数栈的唯一元素即为计算结果  
    return opnd.top();  
}  


【前缀->后缀表达式】

1)操作符栈为空,结果字符串为空。

2)依次读入中缀表达式的每个字符

-如是操作数,添加到结果字符串

-如是左括号,入操作符栈

-如是右括号,弹出栈内符号,添加到结果字符串,直到遇到栈内的左括号。弹出左括号。

-如是操作符,弹出栈内符号,添加懂啊结果字符串,直到遇到左括号,或优先级较低的操作符,或统一优先级的右结合符号。此操作符入栈

3)如到达字符串末尾,弹出所有栈内符号,添加到结果字符串


bool Prior(char optr1, char optr2)  
{  
    bool prior = false;  
  
    if (optr1 == '*' || optr1 == '/')  
        if (optr2 == '+' || optr2 == '-')  
            prior = true;  
  
    return prior;  
}  
  
//前缀表达式->后缀表达式  
string PrefixToPostFix(string exp)  
{  
    string postRet;  
    stack<char> optr;  
    int i = 0;  
    char ch;  
  
    while(i < exp.length())  
    {  
        ch = exp[i++];  
        if (IsOperator(ch))  
        {  
            switch(ch)  
            {  
            case '(':  
                optr.push(ch);  
                break;  
            case ')':  
                //将栈中最近的一个左括号之上的操作符全部弹出,添加到结果  
                while(optr.top() != '(')  
                {  
                    postRet += optr.top();  
                    optr.pop();  
                }  
                optr.pop();//丢弃左括号  
                break;  
            case '+':  
            case '-':  
            case '*':  
            case '/':  
                //弹出操作符,直到栈为空,或遇到左括号,或优先级较低的操作符  
                //或者统一优先级的右结合操作符  
                while (!optr.empty() && Prior(optr.top(), ch))  
                {  
                    postRet += optr.top();  
                    optr.pop();  
                }  
                optr.push(ch);  
                break;  
            }  
        }  
        else  
        {  
            postRet += ch;  
        }  
    }  
  
    //到达字符串末尾,弹出所有操作符,添加到结果  
    while(!optr.empty())  
    {  
        postRet += optr.top();  
        optr.pop();  
    }  
  
    return postRet;  
}  


【后缀表达式求值】

1)初始化操作数栈

2)从左到右依次读入后缀表达式的每个字符,如是操作数,入栈;如是操作符,弹出两个操作数,计算,结果入栈,直到表达式末尾。栈中的唯一数即是结果。注意弹出的第一个操作数是位于运算符右边的数。


//前缀表达式->后缀表达式,再求值  
int CaculateExpression_2(string postExp)  
{  
    //先转换成后缀表达式  
    string exp = PrefixToPostFix(postExp);  
  
    stack<int> opnd;  
    int i = 0;  
    char ch;  
      
    while(i < exp.length())  
    {  
        ch = exp[i++];  
        if(IsOperator(ch))  
        {  
            int num2 = opnd.top();  
            opnd.pop();  
            int num1 = opnd.top();  
            opnd.pop();  
            //计算结果并入栈  
            int ret = Operate(num1, ch, num2);  
            opnd.push(ret);  
        }  
        else  
        {  
            //操作数入栈  
            opnd.push(ch - '0');  
        }  
    }  
  
    return opnd.top();  
}  


【二叉树法】

可以根据前缀表达式,构造出二叉树,后序遍历即得到后缀表达式。

【手动方法】

(A+B)*C-D/(E+F)

1)按照运算符优先级对所有运算单位加括号。(((A+B)*C)-(D/(E+F)))

2)前缀:把运算符移动到对应的括号前面:-(*(+(AB)C)/(D+(EF))),再去掉括号:-*+ABC/D+EF

3)后缀:把运算符移动到对应的括号后面:(((AB)+C)*(D(EF)+)/)-,再去掉括号:AB+C*DEF+/-

参考博客:http://blog.csdn.net/lilypp/article/details/6546658