栈实现字符串加减法

【问题描述】

用字符串输入一个数学表达式，计算出结果并输出

【基本要求】

（1）运算符包括

（2）括号只使用小括号扩回

【数据测试】

（1）(10+10)/(20) result = 1

（2）(100+20)+(30/15) result = 122

【实现提示】

可以通过数据结构中的栈来实现这个操作，具体实现方法为设立两个栈，一个栈用来存放数字，另一个栈用来存放运算符，自左向右扫描表达式遇到数存入数据栈，当遇到运算符时，如果其优先级比当前操作符栈的优先级高的话就将这个操作符压入操作栈，反之，将操作符栈栈顶元素取出，同时取出数据栈的栈顶的两个元素通过去除的操作符进行计算，将结果压入数据栈，将遇到的操作符压入操作符栈。同时遇到左括号就将其压入操作符栈，遇到右括号就取出操作栈栈顶元素以及数据栈栈顶两个元素进行操作，将结果压入数据栈，最后直到取出左括号为止

【问题分析】

栈的实现一般由两种方法，首先是顺序栈，再就是链栈，对于顺序栈来说，就是一个数组，通过下标进行操作，对于链栈来说，博主想到的时通过双向循环链表来实现，但是博主这里选择使用C++里面的

容器来实现栈的一些操作。

main函数里面的定义为

 vector<char> oper;

    vector<int> num;

对于入栈的操作为

 template <class T>//定义一个模板用来完成对两者的入栈操作

    void push_elem(vector<T> &oper,T top_elem){

        oper.push_back(top_elem);    

    }

对于比较优先级的函数为

int my_compare(char ch,vector<char> &oper){//通过返回0，-1，1来判断优先级，0表示需要执行入栈操作，1表示直接跳过，-1表示需要计算    

    if(oper.empty())return 0;

    else{

        if(ch == '(' || (oper.back() == '(' && ch != ')')){

            return 0;                       

        }

        else if((oper.back() == '-' || oper.back() == '+') && (ch == '*' || ch == '/')){

            return 0;                      

        }

        else if (oper.back() == '(' && ch == ')' ){

            oper.pop_back();

            return 1;                      

        }

        else{

            return -1;                                         

        }

    }

}

main函数里面对应的操作为

     while(1){

            i = my_compare(*it,oper);//这里的i为循环外面定义的用来暂时存储返回值的临时变量。

            if(i == 0){

                push_elem(oper,*it);

                break;

            }

            else if(i == 1){

                it++;

            }

            else{

                deal_data(num,oper);

            }   

        }

我们来分析一下，首先当操作栈为空的时候，肯定是只能执行入栈操作的，所以返回0。当判断的操作符为

时，直接入操作栈，或者此时栈顶元素

需要判断的元素不是

，也是直接入栈，再两者都不满足，栈顶元素是优先级较低的

和

，而传入的元素是优先级较高的

和

，那样也执行入栈。

对于需要运算的，那就只有一种情况，就是此时操作栈栈顶元素不是

但是此时传入的元素为

，其他还有一种情况，就是操作栈栈顶元素为

而传入的字符为

，这种情况直接跳过。

再就是处理数据的部分，代码为

void deal_data(vector<int> &num,vector<char> &oper){

    int num_1 = num.back();num.pop_back();

    int num_2 = num.back();num.pop_back();

    

    int value (0);//用来记录的临时变量



    switch(oper.back()){

        case '-': value = num_2 - num_1;break;

        case '*': value = num_1 * num_2;break;

        case '+': value = num_1 + num_2;break;

        case '/': value = num_2 / num_1;break;

    }



    oper.pop_back();//将操作栈的栈顶元素去除

    

    push_elem(num,value);

}

这儿没啥好说的，直接取元素计算，返回就行了。

再就是主函数了

int main(){

    string tmp_input;

    cin>>tmp_input;//输入字符串

    char *input = (char *)malloc(sizeof(char)*(tmp_input.length()+1));

    memset(input,'\0',tmp_input.length()+1);//初始化字符串数组

    strcpy(input,tmp_input.c_str());//对字符串数组赋值

    

    vector<char> oper;

    vector<int> num;

    

    int i(0);

    for(char *it = input;*it != '\0';it++){

        if(isdigit(*it)){

            push_elem(num,atoi(it));

            while(isdigit(*it))it++;

        }

        while(1){

            i = my_compare(*it,oper);

            if(i == 0){

                push_elem(oper,*it);

                break;

            }

            else if(i == 1){

                it++;

            }

            else{

                deal_data(num,oper);

            }   

        }

    }

    cout<<"result = "<<num[0];

    return 0;

}

对于主函数来说输入字符串时选用

类型的变量因为这样可以不限制长度输入，但是后开进行处理的时候博主发现用来将

转化为

的函数

十分鸡肋，的迭代器用起来十分不匹配，所以博主干脆两者都不用，直接换成字符串数组进行操作。

下面是我写的完整的源码

#include <iostream>

#include <string.h>

#include <vector>

#include <stdlib.h>

#include <cctype>



using namespace std;



int my_compare(char ch,vector<char> &oper){    

    if(oper.empty())return 0;

    else{

        if(ch == '(' || (oper.back() == '(' && ch != ')')){

            return 0;                       

        }

        else if((oper.back() == '-' || oper.back() == '+') && (ch == '*' || ch == '/')){

            return 0;                      

        }

        else if (oper.back() == '(' && ch == ')' ){

            oper.pop_back();

            return 1;                      

        }

        else{

            return -1;                                         

        }

    }

}



template <class T>

void push_elem(vector<T> &oper,T top_elem){

    oper.push_back(top_elem);

} 



void deal_data(vector<int> &num,vector<char> &oper){

    int num_1 = num.back();num.pop_back();

    int num_2 = num.back();num.pop_back();

    

    int value (0);



    switch(oper.back()){

        case '-': value = num_2 - num_1;break;

        case '*': value = num_1 * num_2;break;

        case '+': value = num_1 + num_2;break;

        case '/': value = num_2 / num_1;break;

    }



    oper.pop_back();

    

    push_elem(num,value);

}



int main(){

    string tmp_input;

    cin>>tmp_input;

    char *input = (char *)malloc(sizeof(char)*(tmp_input.length()+1));

    memset(input,'\0',tmp_input.length()+1);

    strcpy(input,tmp_input.c_str());

    

    vector<char> oper;

    vector<int> num;

    

    int i(0);

    for(char *it = input;*it != '\0';it++){

        if(isdigit(*it)){

            push_elem(num,atoi(it));

            while(isdigit(*it))it++;

        }

        while(1){

            i = my_compare(*it,oper);

            if(i == 0){

                push_elem(oper,*it);

                break;

            }

            else if(i == 1){

                it++;

            }

            else{

                deal_data(num,oper);

            }   

        }

    }

    cout<<"result = "<<num[0];

    return 0;

}