表达式求值

表达式基础

任何一个表达式都由操作数（operand）、运算符(operator)和界限符（delimiter）组成。其中操作数可以是常数，也可以是被说明为变量或常量的标识符。运算符可以分为算述运算符、关系运算符、逻辑运算符三类。基本界限符有左右括弧和表达式结束符。为叙述方便简洁，在此仅限讨论只含二元运算的算述表达式。可以将这种表达式定为义：

* 表达式 ::= 操作数 运算符 操作数
* 操作数 ::= 简单变量 | 表达式
* 简单变量 ::= 标识符 | 无符号整数

在计算机中，表达式可以有三种不同的标识方法
假设 Exp(表达式) = S1(第一操作数) OP(运算符)S2(第二操作数)
则称：
OP S1 S2 为表达式的前缀表示方法
S1 OP S2 为表达式的中缀表示方法
S1 S2 OP 为表达式的后缀表示方法

例：已知表达式 Exp = a b + (c - d/ e) f则：
前缀表达式为： + ab -c/def
中缀表达式为： a b +c - d/e f
后缀表达式为： ab cde/-f+

在不同的表示方法中，操作数之间的相对顺序不变，但运算符之间的相对次序是不同。其中，中缀表达式丢失了原表达式的括弧信息致运算的次序不确定没有用外，前缀和后缀表达式中都包含了确定的运算顺序。
它们的运算规则如下：

前缀表达式：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成最小表达式
后缀表达式：每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式，且运算符在后缀表达式中出现的顺序恰为表达式的运算顺序。

后缀表达式求值算法

因此从后缀表达式很容易求得表达式的值，只要“从左至右”顺序扫描后缀表达式，在扫描过程中，凡遇到运算符即做运算，与它对应的操作数应该是在它之前“刚刚”扫描的两个操作数。

为识别“刚刚”扫描过的操作数，自然需要一个栈，以实现操作数“后出现先运算”的规则。因此后缀表达式的求值算法如下：
算法中以字符串表示算述表过式，表达式尾添加#字符作为结束标识。为简单起见，限定操作数以单个字符作为变量名。从左至右依次识别字符串中的字符，若“字母”则“入栈”，否则从栈中退出第二操作数和第一操作数并作相应运算，operator(S1,OP,S2)返回S1和S2进行OP运算的结果。opMember(char ch)为自定义的，返回bool值的函数，若ch为运算符则返回true,否则返回false

#include <stack>
double operate(double S1,char op ,double S2){
    double value = 0;
    switch (op) {
        case '+':
            value = S1 + S2;
            break;
        case '-':
            value = S1 - S2;
            break;
        case '*':
            value =  S1 * S2;
            break;
        case '/':
            value =  S1 / S2;
            break;
    }
    return value;
}
bool OpMember(char ch){
    if (ch == '+' || ch == '-' || ch == '*' || ch =='/' || ch == '(' || ch == ')' || ch == '#') {
        return true;
    }
    return false;
}
double evaluation(char suffix[]){
    using namespace std;
    ///取表达式中第一个字符
    char ch  = *suffix++;
    ///初始空栈
    stack<double> suffixStack;
    while (ch != '#') {
        if (!OpMember(ch)) {
            ///非操作符则入栈
            suffixStack.push(ch);
        }else{
            ///退出两栈顶操作数
            double b = suffixStack.top();
            suffixStack.pop();
            double a  = suffixStack.top();
            suffixStack.pop();
            ///作相应的运算
            double rs = operate(a, ch , b);
            ///操作结果入栈
            suffixStack.push(rs);
        }
        ch = *suffix++;///继续取下一个字符
    }
    if (!suffixStack.empty()) {
        double rs  = suffixStack.top();
        suffixStack.pop();
        return rs;
    }
    return 0;
}

原表达式转后缀表达式

如何从原表达式求得后缀表达式呢？

分析“原表达式”和“后缀表达式”中相应的运算符所在的不同位置可见，原表达式中的运算符在后缀表达式中出现的位置取决于它本身和后一个运算符的优先关系。按照运算符的运算规则：

先乘除、后加减速
从左算到右
先括弧内、后括弧外

运算符	#	(	+	-	)	*	/	^乘幂
优先数	-1	0	1	1	2	2	2	3

若当前运算符的优先级小于在它后面的运算符，则暂不送往后缀表达式，否则它在后缀表达式中领先于在它后面的运算符。换句话说。在后缀表达式中，优先级高的运算符领先于优先级低的运算符。因此从原表达式求得后缀表达式的规则为：

设立运算符栈
设表达式的结束符为“#”，预设运算符栈的栈底为“#”
若当前字符中操作数，则直接发后缀表达式
若当前字符为运算符且优先级大于栈顶运算符，则进栈；否则退出栈顶运算符发送给后缀表达式
若当前是结束符，则自栈顶至栈底依次将栈中所有运算符发送给后缀表达式
“(”对它之前后的运算符起隔离作用，若当前运算符为“(”时进栈
“)”可视为自相应左括弧开始的表达式的结束符，则栈顶起依次退出栈顶运算符发送给后缀表达式，直至栈顶运算符为“(”为止

bool precedOperator(char op1, char op2){
    using namespace std;
    map<char, int> operatormap;
    operatormap.insert(pair<char, int>('#',-1));
    operatormap.insert(pair<char, int>('(',0));
    operatormap.insert(pair<char, int>('+',1));
    operatormap.insert(pair<char, int>('-',1));
    operatormap.insert(pair<char, int>(')',2));
    operatormap.insert(pair<char, int>('*',2));
    operatormap.insert(pair<char, int>('/',2));
    operatormap.insert(pair<char, int>('^',3));
    map<char, int>::iterator iter;
    iter =  operatormap.find(op1);
    int op1value = iter->second ;
    iter =  operatormap.find(op2);
    int op2Value =iter->second;
    if (op1value >= op2Value) {
        return true;
    }
    return false;
}

void transformExp(char suffix[], char exp[]){
    ///从合法的表达木式字符串exp求得其相应的后缀表达式字符串suffix
    using namespace std;
    stack<char> suffixStack;
    stack<char> operatorStack;
    char *p  = exp;
    char ch = *p;
    operatorStack.push('#');///预设运算符栈底元素为#
    while (!operatorStack.empty()) {
        if (!OpMember(ch)) {
            suffixStack.push(ch);///操作数直接发给后缀表达式栈
        }else{
            switch (ch) {
                case '(':
                    operatorStack.push(ch);///左括弧进栈
                    break;
                case ')':{
                    char op = operatorStack.top();
                    while (op != '(') {///自栈顶大至左括弧之前的运算符发送给后缀栈
                        suffixStack.push(op);
                        operatorStack.pop();
                        op = operatorStack.top();
                    }
                    if (op  == '(') {
                        operatorStack.pop();
                    }
                }
                    break;
                default:
                    char op  = operatorStack.top();
                    bool value =  precedOperator(op, ch);
                    while (op && value) {
                        suffixStack.push(op);
                        operatorStack.pop();
                        if (!operatorStack.empty()) {
                            op = operatorStack.top();
                            value =  precedOperator(op, ch);
                        }else{
                            value = false;
                        }
                    }
                    //将栈中所有优先级不小于当前运算符优先级的运算符发给后缀表达式
                    if (ch != '#') {
                        operatorStack.push(ch);//优先级大于栈顶元素的运算符入栈
                    }
                    break;
            }

        }
        ch = *++p;///下一个字符处理
        if (ch == '#') {
            break;
        }
    }
    while (!operatorStack.empty()) {//将运算符栈的剩余操作符发给后缀表达式
        suffixStack.push(operatorStack.top());
        operatorStack.pop();
    }
    stack<char> op;
       while (!suffixStack.empty()) {
        ///将表达式栈逆转过来
        op.push(suffixStack.top());
        std::cout<<suffixStack.top()<<" ";
        suffixStack.pop();
    }
    std::cout <<endl;
    char *rs  = suffix;
    while (!op.empty()) {
        *rs++ = op.top();
        std::cout<<op.top()<<" ";
        op.pop();
    }
    std::cout <<endl;
}