表达式求值

溯影

《数据结构C++描述》清华大学出版社  任燕编著

小弟简单改写了书上的程序，使之可以运行，同时在顺序栈那里也是改了书上的一个bug
程序小弟调试了应该没有错，要是有错欢迎来指出，
数据结构真有意思，嘿嘿

从大约190行开始时逆波兰表达式的转化和求值的一些函数
之前的顺序栈的定义和一些方法可以滤去不看（若是您很清楚的话）
在输入表达式值的时候建议要用英文状态下的字符，同时不要有空格

#include <iostream>
#include <assert.h>
#include <cstdlib>
#include <cstdbool>
#define STACK_MAX_SIZE 100
#define STACKINCREAMENT 10
using namespace std;
///////////////////////////////////////////////////////////
//栈的结构定义和一些方法的应用
template <typename elemtype>
class SqStack{
public:
        //顺序栈置空
        void clear();

        //求顺序栈中元素的个数
        int getLength();

        //返回档期那已经分派的存储空间的大小
        int getStackSize();

        //读取栈顶元素
        bool getTop(elemtype &e);

        //判断顺序栈是否为空
        bool isEmpty();

        //重载赋值运算符
        SqStack operator=(SqStack right);

        //弹出栈顶元素
        bool pop(elemtype &e);

        //在栈顶压入元素e
        void push(elemtype e);

        //构造函数
        SqStack();

        //析构函数
        virtual ~SqStack();

        //拷贝构造函数
        SqStack(SqStack &other);

        //重载输出运算符
        template <typename out_put>
        friend ostream& operator <<(ostream& out, SqStack<out_put> other);

protected:
        elemtype *base;//栈底指针，就是顺序栈动态存储空间的首地址
        elemtype *top;//栈顶指针
        int stackSize;//顺序栈当前已经分配的存储空间的大小
};


template <typename elemtype>
void SqStack<elemtype>::clear(){
        top = base;
        cout << "顺序栈已经清空" << endl;
}

template <typename elemtype>
int SqStack<elemtype>::getLength(){
        return top - base;
}

template <typename elemtype>
int SqStack<elemtype>::getStackSize(){
        return stackSize;
}

//读取栈顶的元素
template <typename elemtype>
bool SqStack<elemtype>::getTop(elemtype &e){
        if (isEmpty()){
                return false;
        }
        else{
                e = *(top - 1);
        }
        return true;
}

template <typename elemtype>
bool SqStack<elemtype>::isEmpty(){
        return top == base ? true : false;
}

//重载赋值运算符
template <typename elemtype>
SqStack<elemtype> SqStack<elemtype>::operator =(SqStack<elemtype> right){
        int length = right.getLength();

        if (this != &right){
                if (stackSize < right.stackSize){
                        delete[] base;  //回收左边的顺序栈的存取空间
                        base = new elemtype[right.stackSize];
                        assert(base != 0);
                        stackSize = right.stackSize;//进行属性的一些重新的赋值
                }

                for (int i = 0; i < length; i++){
                        *(base + i) = *(right.base + i);
                }
                top = base + length();
        }
        return *this;//返回对象
}

//弹出栈顶元素到e
template <typename elemtype>
bool SqStack<elemtype>::pop(elemtype &e){
        if (isEmpty()){
                return false;
        }
        else{
                e = *--top;
        }
        return true;
}

//在栈顶压入元素e
template <typename elemtype>
void SqStack<elemtype>::push(elemtype e){
        int length = top - base;//顺序栈中元素的个数
        elemtype *newBase;//预指向新顺序栈的栈底指针
        //判断当前顺序栈是否已满，如果满了，则需要另外申请存储空间
        if (top - base >= stackSize){
                newBase = new elemtype[stackSize + STACKINCREAMENT];
                assert(newBase != 0);

                for (int j = 0; j < length; j++){
                        *(newBase + j) = *(base + j);
                }

                delete[] base;//回收当前已经满了的栈空间
                base = newBase;
                top = base + length;
        }

        //如果当前顺序栈没有满，就不用重新申请空间了，就直接以下两个语句就行了
        *top = e;
        top++;
}


template <typename elemtype>
SqStack<elemtype>::SqStack(){
        base = new elemtype[STACK_MAX_SIZE];//申请空间
        assert(base != 0);
        stackSize = STACK_MAX_SIZE;//属性的赋值
        top = base;//栈的初始为空
}

//你懂的
template <typename elemtype>
SqStack<elemtype>::~SqStack(){
        if (base){
                delete[]base;
        }
        stackSize = 0;
        top = base = NULL;
}

template <typename elemtype>
SqStack<elemtype>::SqStack(SqStack &other){
        int length = other.top - other.base;
        base = new elemtype[other.stackSize];

        assert(base != 0);

        stackSize = other.stackSize;
        for (int i = 0; i < length; i++){
                *(base + i) = *(other.base + i);
        }
        top = base + length;
}

template <typename out_put>
ostream& operator<<(ostream& out, SqStack<out_put> other){
        int length = other.top - other.base;
        for (int i = 0; i < length; i++){
                out << *(other.base + i) << "\t";
        }

        return out;
}



/////////////////////////////////////////////////////////////////
//下面开始写中缀表达式向后缀表达式的函数

//判断是运算符，数字字符或者是其他的字符
int isOpMember(char ch){
        if (ch == '0' || ch == '1' ||
                ch == '2' || ch == '3' ||
                ch == '4' || ch == '5' ||
                ch == '6' || ch == '7' ||
                ch == '8' || ch == '9'){
                return 0;
        }
        else if (ch == '+' || ch == '-' ||
                ch == '*' || ch == '/' ||
                ch == '(' || ch == ')' ||
                ch == '\0'){
                return 1;
        }
        else{
                return -1;
        }
}


//各种运算符在运算符优先级矩阵的对应的下标
int order(char m){
        switch (m){
        case '+':return 0;
        case '-':return 1;
        case '*':return 2;
        case '/':return 3;
        case '(':return 4;
        case ')':return 5;
        case '\0':return 6;
        default:return 7;
        }
}


//判定两个运算符的优先级的高低
int precede(char op1, char op2){
        //运算符优先级矩阵
        int inCmpOut[7][7] = { { 1, 1, -1, -1, -1, 1, 1 },
        { 1, 1, -1, -1, -1, 1, 1 },
        { 1, 1, 1, 1, -1, 1, 1 },
        { 1, 1, 1, 1, -1, 1, 1 },
        { -1, -1, -1, -1, -1, 0, 0 },
        { 1, 1, 1, 1, 2, 1, 1 },
        { -1, -1, -1, -1, -1, 2, 0 } };
        int i, j;
        i = order(op1);//op1在矩阵中的下标，作为行号
        j = order(op2);//op2在矩阵中的下标，作为列号
        return inCmpOut[i][j];
}

//中缀表达式转化为后缀表达式
//输入：函数的参数midS为待转换的中缀表达式
//输出：函数的参数suffixS为midS对应的后缀表达式
void transform(char *midS, char *suffixS){
        int i = 0;//后缀表达式当前处理字符的下标，初始化为0
        int j = 0;//中缀表达式当前处理字符的下标，初始化为0
        char ch = midS[0];//中缀表达式当前处理字符，初始化为第一个字符
        //中缀表达式转化为后缀的过程中，遇到运算符是不能直接进入到后缀表达式中的
        //他们要让后面较高级别的运算符先进入，所以用运算符栈S先暂存这些
        //还不能进入到后缀表达式的运算符
        SqStack<char> S;
        char op;//预存放运算符栈S弹出的栈顶元素

        //把运算符'\0'压栈，它是最低级别的运算符，如果最后弹出此运算符，则表明已经完成转化
        S.push('\0');

        //从中缀表达式的第一个字符开始，知道结束，逐一扫描，分别转化
        while (!S.isEmpty()){
                if (!isOpMember(ch)){//如果是操作数
                        if (i > 0 && isOpMember(suffixS[i - 1]) == 1){
                                suffixS[i++] = ' ';//如果是新操作数，就添加空格
                        }
                        suffixS[i++] = ch;//直接进入后缀表达式
                }
                else{//如果是运算符
                        if (i > 0 && suffixS[i - 1] != ' '){
                                suffixS[i++] = ' ';
                        }
                        switch (ch){
                        case '('://左括号直接入栈
                                S.push(ch);
                                break;
                        case ')':
                                S.pop(op);
                                while (op != '('){
                                        suffixS[i++] = op;
                                        suffixS[i++] = ' ';
                                        S.pop(op);
                                }
                                --i;//回到原来i的位置
                                break;
                        default://其他情况的运算符例如+-*/等
                                while (S.getTop(op)){
                                        if (precede(op, ch) == 1 || precede(op, ch) == 0){
                                                suffixS[i++] = op;
                                                suffixS[i++] = ' ';
                                        }
                                        else{
                                                break;
                                        }
                                        S.pop(op);//写入后缀表达式后要弹栈
                                }
                                //如果中缀表达式当前字符不是'\0',则压入运算符栈
                                if (ch != '\0'){
                                        S.push(ch);
                                }
                        }
                }
                if (ch != '\0'){
                        ch = midS[++j];
                }
        }
        suffixS[i] = '\0';//放入最后一个单元，完成转化
}

//指定运算符的运算
double caculate(double a, char ch, double b){
        switch (ch){
        case '+':return a + b;
        case '-':return a - b;
        case '*':return a*b;
        case '/':return a / b;
        default:return -1;
        }
}


//后缀表达式的计算
double evaluation(char *suffixS){
        int i = 0;//后缀表达式的当前字符的下标，初始化为0
        char ch = suffixS[i];//后缀表达式当前字符，初始化为第一个字符
        double x;//预存放当前操作数

        SqStack<double> S;//后缀表达式中计算的时候要用到顺序栈来进行运算
        double a, b;

        //从后缀表达式的第一个字符开始，直到结束，分别处理
        while (ch != '\0'){
                if (isOpMember(ch) == 0){
                        x = 0;
                        while (isOpMember(ch) == 0){//如果当前是操作数
                                x = 10 * x + (ch - '0');
                                ch = suffixS[++i];
                        }
                        S.push(x);
                }
                else if (isOpMember(ch) == 1){//如果当前是运算符
                        S.pop(b);
                        S.pop(a);
                        S.push(caculate(a, ch, b));
                }
                ch = suffixS[++i];
        }
        S.pop(x);//从栈中弹出结果
        return x;//返回结果
}


int main(void){
        char midS[128];
        char suffixS[128];
        cout << "请输入一个表达式:" << endl;
        cin >> midS;
        transform(midS, suffixS);//调用中缀表达式转化为后缀表达式的函数
        cout << "后缀表达式为:" << endl;
        cout << suffixS << endl;
        cout << "计算结果为:" << endl;
        cout << evaluation(suffixS) << endl;
        return 0;
}

运行结果:
请输入一个表达式:
23-((34-13)*7+6/2)
后缀表达式为:
23 34 13 - 7 * 6 2 / + -
计算结果为:
-127
请按任意键继续. . .