【数据结构】表达式求值

预习文档
参考文档

正确版本1

经过我这么多天的努力，我终于！！终于写出来了能够正确运行的代码，但是还是仿照着写的，并不是自己的思路。以后就用C++了，用好一把兵器，不断打磨。

sqStack.cpp

//
// Created by 63400 on 2021/11/1.
//
#include 
#include "linkStack.h"
using namespace std;

int main()
{
    DoubleStack optrStack;
    CharStack opndStack;

    cout << "请输入算数表达式以#结束" << endl;
    cout<< evaluateexpression(optrStack, opndStack);

    return 0;

}

linkStack.h

//
// Created by 63400 on 2021/11/1.
//

#ifndef HOMEWORK_linkSTACK_H
#define HOMEWORK_linkSTACK_H
#define MAXSIZE 200
#include 
#include 
using namespace std;

template
class linkStack {
private:
    T *data;
    int top;
    int capacity;

public:
    linkStack();           //无参构造函数
    linkStack(int sz);           //有参构造函数
    ~linkStack();  //析构函数
    void push(T x); //压入一个栈节点
    T getTop();     //得到最后一个节点内容
    T pop();        //弹出最后一个节点的内容
    bool isEmpty();          //判断是否为空栈
    bool isFull();          //判断栈满
    class Empty { }; //设置异常类
    class Full { }; //设置异常类
};

typedef linkStack CharStack;
typedef linkStack DoubleStack;
double evaluateexpression(DoubleStack &opndStack, CharStack &optrStack);//为什么要有这一语句
#endif //HOMEWORK_linkSTACK_H

linkStack.cpp

//
// Created by 63400 on 2021/11/1.
//

#include 
#include "linkStack.h"

using namespace std;

template
linkStack::linkStack() {
    data = new T[MAXSIZE];
    top = -1;
    capacity = MAXSIZE;
}

template
linkStack::linkStack(int sz) {
    data = new T[sz];
    top = -1;
    capacity = sz;
}

template
linkStack::~linkStack() {
    delete[] data;
}

template
void linkStack::push(T x) {
    if (isFull()) {
        throw Full();
    } else {
        data[++top] = x;   //top值先+1，然后压入
    }
}

template
T linkStack::pop() {
    if (isEmpty()) { throw Empty(); }
    else { return data[top--]; }

}

template
T linkStack::getTop() {
    if (isEmpty()) { //不为空
        throw Empty();
    } else {
        return data[top];
    } //返回top内容
}

template
bool linkStack::isEmpty() {
    if (top == -1) {
        return true;
    } else {
        return false;
    }
}

template
bool linkStack::isFull() {
    if (top == MAXSIZE - 1) {
        return true;
    } else {
        return false;
    }
}

template
class linkStack;

template
class linkStack;


//判断是否为数字
bool isOpnd(char ch) {
    const int lenofOpnd = 10;
    char Opnd[lenofOpnd] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    for (int i = 0; i < lenofOpnd; ++i) {
        if (ch == Opnd[i]) return true;
    }
    return false;
}

//判断是否为操作符
bool isOptr(char ch) {
    const int lenofOptr = 8;
    //必须有const，数组的空间是在程序启动时就已经静态分配好了
    char Optr[lenofOptr] = {'+', '-', '*', '/', '(', ')', '#'};
    for (int i = 0; i < lenofOptr; ++i) {
        if (ch == Optr[i])
            return true;
    }
    return false;
}

//计算操作函数
double operate(double a, char optr, double b) {
    if (isOptr(optr)) {
        switch (optr) {
            case '+':
                return a + b;
                break;
            case '-':
                return a - b;
                break;
            case '*':
                return a * b;
                break;
            case '/':
                return (double) (a) / (double) (b);
                break;
        }
    }
}

//查找两个运算符之间的优先级
char precede(char first, char second) {
    //运算优先表/
#define M 8
#define N 8
    char CalPriority[M][N] =
            {0, '+', '-', '*', '/', '(', ')', '#',
             '+', '>', '>', '<', '<', '<', '>', '>',
             '-', '>', '>', '<', '<', '<', '>', '>',
             '*', '>', '>', '>', '>', '<', '>', '>',
             '/', '>', '>', '>', '>', '<', '>', '>',
             '(', '<', '<', '<', '<', '<', '=', 0,
             ')', '>', '>', '>', '>', 0, '>', '>',
             '#', '<', '<', '<', '<', '<', 0, '='
            };

    int num1 = 0, num2 = 0;
    for (; num1 < M; num1++) {
        if (CalPriority[0][num1] == first)
            break;
    }
    for (; num2 < M; num2++) {
        if (CalPriority[num2][0] == second)
            break;
    }
    return CalPriority[num1][num2];
}

double evaluateexpression(DoubleStack &opndStack, CharStack &optrStack) {
//opnd 操作数栈 optr运算符栈
    char ch, optr;
    double num1, num2, res, temp;
    int isNum = 0;//判断前一个字符是否为数字
    cin >> ch;
    optrStack.push('#');
    if('#' == ch){
        cout<< "头部不能是#"<> ch;
            } else {
                isNum = 1;
                opndStack.push(ch - '0');
                cin >> ch;
            }

        } else//操作符，比较优先级
        {
            isNum = 0;
            switch (precede(optrStack.getTop(), ch)) {
                case '>'://栈顶元素出栈，操作数栈弹出2个元素
                    num1 = opndStack.pop();
                    num2 = opndStack.pop();
                    optr = optrStack.pop();
                    res = operate(num1, optr, num2);
                    opndStack.push(res);
                    break;
                case '<':
                    optrStack.push(ch);
                    cin >> ch;
                    break;
                case '=':
                    optrStack.pop();
                    cin >> ch;
                    break;
            }
        }
    }
    return opndStack.pop();
}

正确版本2 sqStack.cpp

//
// Created by 63400 on 2021/11/1.
//
#include 
#include "linkStack.h"
using namespace std;

int main()
{
    DoubleStack optrStack;
    CharStack opndStack;

    cout << "请输入算数表达式以#结束" << endl;
    string input;
    cin>>input;
    cout< 
linkStack.h 
//
// Created by 63400 on 2021/11/1.
//

#ifndef HOMEWORK_linkSTACK_H
#define HOMEWORK_linkSTACK_H
#define MAXSIZE 200
#include 
#include 
using namespace std;

template
class linkStack {
private:
    T *data;
    int top;
    int capacity;

public:
    linkStack();           //无参构造函数
    linkStack(int sz);           //有参构造函数
    ~linkStack();  //析构函数
    void push(T x); //压入一个栈节点
    T getTop();     //得到最后一个节点内容
    T pop();        //弹出最后一个节点的内容
    bool isEmpty();          //判断是否为空栈
    bool isFull();          //判断栈满
    class Empty { }; //设置异常类
    class Full { }; //设置异常类
};

typedef linkStack CharStack;
typedef linkStack DoubleStack;
double evaluateexpression(DoubleStack &opndStack, CharStack &optrStack,string input);//为什么要有这一语句
#endif //HOMEWORK_linkSTACK_H

 
linkStack.cpp 
//
// Created by 63400 on 2021/11/1.
//

#include 
#include "linkStack.h"

using namespace std;

template
linkStack::linkStack() {
    data = new T[MAXSIZE];
    top = -1;
    capacity = MAXSIZE;
}

template
linkStack::linkStack(int sz) {
    data = new T[sz];
    top = -1;
    capacity = sz;
}

template
linkStack::~linkStack() {
    delete[] data;
}

template
void linkStack::push(T x) {
    if (isFull()) {
        throw Full();
    } else {
        data[++top] = x;   //top值先+1，然后压入
    }
}

template
T linkStack::pop() {
    if (isEmpty()) { throw Empty(); }
    else { return data[top--]; }

}

template
T linkStack::getTop() {
    if (isEmpty()) { //不为空
        throw Empty();
    } else {
        return data[top];
    } //返回top内容
}

template
bool linkStack::isEmpty() {
    if (top == -1) {
        return true;
    } else {
        return false;
    }
}

template
bool linkStack::isFull() {
    if (top == MAXSIZE - 1) {
        return true;
    } else {
        return false;
    }
}

template
class linkStack;

template
class linkStack;


//判断是否为数字
bool isOpnd(char ch) {
    const int lenofOpnd = 10;
    char Opnd[lenofOpnd] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    for (int i = 0; i < lenofOpnd; ++i) {
        if (ch == Opnd[i]) return true;
    }
    return false;
}

//判断是否为操作符
bool isOptr(char ch) {
    const int lenofOptr = 8;
    //必须有const，数组的空间是在程序启动时就已经静态分配好了
    char Optr[lenofOptr] = {'+', '-', '*', '/', '(', ')', '#'};
    for (int i = 0; i < lenofOptr; ++i) {
        if (ch == Optr[i])
            return true;
    }
    return false;
}

//计算操作函数
double operate(double a, char optr, double b) {
    if (isOptr(optr)) {
        switch (optr) {
            case '+':
                return a + b;
                break;
            case '-':
                return a - b;
                break;
            case '*':
                return a * b;
                break;
            case '/':
                return (double) (a) / (double) (b);
                break;
        }
    }
    return 0;
}

//查找两个运算符之间的优先级
char precede(char first, char second) {
    //运算优先表/
#define M 8
#define N 8
    char CalPriority[M][N] =
            {0, '+', '-', '*', '/', '(', ')', '#',
             '+', '>', '>', '<', '<', '<', '>', '>',
             '-', '>', '>', '<', '<', '<', '>', '>',
             '*', '>', '>', '>', '>', '<', '>', '>',
             '/', '>', '>', '>', '>', '<', '>', '>',
             '(', '<', '<', '<', '<', '<', '=', 0,
             ')', '>', '>', '>', '>', 0, '>', '>',
             '#', '<', '<', '<', '<', '<', 0, '='
            };

    int num1 = 0, num2 = 0;
    for (; num1 < M; num1++) {
        if (CalPriority[0][num1] == first)
            break;
    }
    for (; num2 < M; num2++) {
        if (CalPriority[num2][0] == second)
            break;
    }
    return CalPriority[num1][num2];
}

double evaluateexpression(DoubleStack &opndStack, CharStack &optrStack,string input) {
//opnd 操作数栈 optr运算符栈
    char ch, theta;
    double num1, num2,temp;
    int chcount,multiply = 1;

    ch = input[chcount];

    optrStack.push('#');
    if ('#' == ch) {
        cout << "头部不能是#" << endl;
        exit(0);
    }

    do {
        if (isOptr(ch)) { //如果是运算符
            if(multiply != 1)  //避免重复压入
            {
                opndStack.push(temp);  //ascii 转 数字   -48

                multiply = 1;
                temp = 0;
            }

            //比较运算符栈的栈顶元素和ch的关系 ,此时ch必须是运算符才能进入if
            switch (precede(optrStack.getTop(), ch)) {
                case '<':
                    optrStack.push(ch);//压入运算符栈
                    ch = input[++chcount];
                    break;
                case '=':
                //只有（）才会遇到等于的情况，此时的作用是将表达式中的（）消除掉
                if(ch == ')'){optrStack.pop();}
                ch = input[++chcount];
                    break;
                case '>':
                    theta = optrStack.pop(); //theta存放运算符栈的栈顶元素
                    num2 = opndStack.pop(); //b存放操作数栈的栈顶元素
                    num1 = opndStack.pop(); //a存放操作数栈的栈顶元素的下一元素

                    opndStack.push(operate(num1, theta, num2));//所得结果压入操作数栈
                    break;
            }
        }else{//如果不是运算符
            if (ch == ' ') //如果ch是空格,后移一位
            { ch = input[++chcount]; }

                // char类型的数字转换成int型的数字
            else if (isOpnd(ch))  //如果ch是操作数，压入操作数栈
            {

                temp = temp * multiply + (ch - 48);
                multiply = 10;
                ch = input[++chcount];  //此时char类型的数字转换成int型的数字
            }
            else
            {
                cout << "存在非法字符" << endl;
                exit(0);
            }
        }
    }while ((ch != '#') or (optrStack.getTop() != '#'));


    return opndStack.getTop();
}

 
 
错误版本 
下面这个程序是错误的，但是！！正确的已经被我改好了，即上文的正确版本2。哈哈哈哈太开心了！ 
sqStack.cpp 
//
// Created by 63400 on 2021/11/1.
//
#include 
#include "linkStack.h"
using namespace std;
int main()
{
    string input = "5+5*4*(5-2)+6 #";
    //cout << "输入多项式计算 以'#'结尾" << endl;
    //cin  >>input;  //手动输入
    //cout <<"输入的多项式为 "<< input << endl;
    cout << input ;
    cout <<"result ="< 
linkStack.h 
//
// Created by 63400 on 2021/11/1.
//

#ifndef HOMEWORK_linkSTACK_H
#define HOMEWORK_linkSTACK_H

#include 
#include 
using namespace std;

template
class linkStack {
private:
//    struct Node * top;   //链表节点指针
   static int linkCount;

    typedef struct Node {
        T data;
        struct Node *next;
    }node,* link;

    link top;

public:
    linkStack();           //构造函数
    virtual ~linkStack();  //析构函数
    void push(T x); //压入一个栈节点
    T gettop();     //得到最后一个节点内容
    T pop();        //弹出最后最后一个节点的内容
    bool isEmpty();          //判断是否为空栈
//    int getlinkCount();    //输出节点数量
    void setNull(); //置空
};

double Calmultinomial(string input); //计算多项式函数
bool isOptr(char input); //是否为运算符
bool isOpnd(char input); //是否为操作数
double operate(double a,char optr,double b);//计算操作函数 返回-1无效
char precede(char first,char second);//查表函数  使用前判断是否都为运算符

#endif //HOMEWORK_linkSTACK_H


 
linkStack.cpp 
//
// Created by 63400 on 2021/11/1.
//

#include "linkStack.h"
#include 

using namespace std;

template
int linkStack::linkCount = 0;  //节点记录数字

template
linkStack::linkStack() {
    //struct Node * s = top;
    link s;
    s = new node;
    top = s; //改动
    s->next = nullptr;
}

template
linkStack::~linkStack() {
    for (int i = 0; i < linkCount; ++i) {
        //       struct Node *p = top;
        link p = top;
        top = top->next;
        delete p;
    }
}

template
void linkStack::push(T x) {
    //  struct Node *s = new Node;
    link s;
    s = new node;
    s->data = x;
    s->next = top;
    top = s;
    linkCount++;
}

template
T linkStack::pop() {

    if (NULL == top) return -1;
    T m = top->data;
    link p = top;
    top = top->next;
    delete p;
    return m;

}

template
T linkStack::gettop() {
    if (!isEmpty()) { //不为空
        return top->data;  //返回top内容
    }
}

template
bool linkStack::isEmpty() {
    return top == nullptr;
}

//template
//int linkStack::getlinkCount() {
//    return linkCount;
//}

template
void linkStack::setNull() {
    top = nullptr;
}

double Calmultinomial(string input) {
    linkStack OPTR; //运算符栈
    linkStack OPND; //操作数栈
    char theta;
    double a, b, out, number = 0;
    //int multiply = 1; //累加倍率， 不懂
    char ch;
    int chcount = 0; //表达式input的下标，从0开始


    OPTR.setNull();
    OPND.setNull();


    ch = input[chcount]; //ch为input表达式的第一个
    OPTR.push('#'); //压入‘#’
    if (ch == '#') {
        cout << "表达式的头部不能是#" << endl;
        //return 0; //改动
        exit(0);
    }

    do {

        if (isOptr(ch)) {   //如果是运算符
            switch (precede(OPTR.gettop(), ch)) {
                //比较运算符栈的栈顶元素和ch的关系 ,此时ch必须是运算符才能进入if
                case '<':
                    OPTR.push(ch); //压入运算符栈
                    ch = input[++chcount];
                    break;

                case '>':
                    theta = OPTR.pop(); //theta存放运算符栈的栈顶元素
                    b = OPND.pop(); //b存放操作数栈的栈顶元素
                    a = OPND.pop(); //a存放操作数栈的栈顶元素的下一元素

                    cout << a;
                    cout << theta;
                    cout << b;
                    cout << "=" << operate(a, theta, b) << endl;

                    OPND.push(operate(a, theta, b));//所得结果压入操作数栈
                    break;
                case '=':
                    //只有（）才会遇到等于的情况，此时的作用是将表达式中的（）消除掉
                    if (ch == ')') { OPTR.pop(); }
                    ch = input[++chcount];
                    break;
            }
        } else {  //如果不是运算符
            if (ch == ' ') //如果ch是空格,后移一位
            { ch = input[++chcount]; }

                // char类型的数字转换成int型的数字
            else if (isOpnd(ch))  //如果ch是操作数，压入操作数栈 //标记
            {
                int multiply = 10;  //改动
                number = number * multiply + (ch - 48);
                //char类型的数字转换成int型的数字
                ch = input[++chcount];
                OPND.push(number);  //此时char类型的数字转换成int型的数字

            }
            else
            {
                cout << "存在非法字符" << endl;
                exit(0);
            }

        }


    } while ((ch != '#') or (OPTR.gettop() != '#'));

    return OPND.gettop();
}

//判断是否为操作符
bool isOptr(char input) {
    const int lenofOptr = 8;
    //必须有const，数组的空间是在程序启动时就已经静态分配好了
    char Optr[lenofOptr] = {'+', '-', '*', '/', '(', ')', '#'};
    for (int i = 0; i < lenofOptr; ++i) {
        if (input == Optr[i])
            return true;
    }
    return false;
}


//判断是否为数字
bool isOpnd(char input) {
    const int lenofOpnd = 10;
    char Opnd[lenofOpnd] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    for (int i = 0; i < lenofOpnd; ++i) {
        if (input == Opnd[i]) return true;
    }
    return false;
}

//计算操作函数
double operate(double a, char optr, double b) {
    if (isOptr(optr)) {
        switch (optr) {
            case '+':
                return a + b;
                break;
            case '-':
                return a - b;
                break;
            case '*':
                return a * b;
                break;
            case '/':
                return (double) (a) / (double) (b);
                break;
        }
    }
    return -1;
}

//查找两个运算符之间的优先级
char precede(char first, char second) {
    //运算优先表/
#define M 8
#define N 8
    char CalPriority[M][N] =
            {0, '+', '-', '*', '/', '(', ')', '#',
             '+', '>', '>', '<', '<', '<', '>', '>',
             '-', '>', '>', '<', '<', '<', '>', '>',
             '*', '>', '>', '>', '>', '<', '>', '>',
             '/', '>', '>', '>', '>', '<', '>', '>',
             '(', '<', '<', '<', '<', '<', '=', 0,
             ')', '>', '>', '>', '>', 0, '>', '>',
             '#', '<', '<', '<', '<', '<', 0, '='
            };

    int num1 = 0, num2 = 0;
    for (; num1 < M; num1++) {
        if (CalPriority[0][num1] == first)
            break;
    }
    for (; num2 < M; num2++) {
        if (CalPriority[num2][0] == second)
            break;
    }
    return CalPriority[num1][num2];
}


template
class linkStack;

template
class linkStack;
 
不对，不对。有很多不对的地方。
 我感觉我好差劲，我好笨。 
1.不要复制代码。
 2.耐下心来，一定要慢下来。

【数据结构】表达式求值

C/C++/C#相关栏目本月热门文章