C++四则运算字符串解析（附动图以及动图制作方法）

落日映苍穹つ 2022-10-22 04:29 226阅读 0赞

## 题目描述 ##

> 输入一个表达式（用字符串表示），求这个表达式的值。
> 
> 保证字符串中的有效字符包括\[‘0’-‘9’\],‘+’,‘-’, ‘\*’,‘/’ ,‘(’， ‘)’,‘\[’, ‘\]’,‘\{’ ,‘\}’。且表达式一定合法。

> 输入：+3+2\*\{1+2\*\[-4/(8-6)+7\]\}
> 
> 输出：25

# 思路 #

1.  使用两个栈来维护计算过程：一个数字栈，用来存储操作数字；一个操作符栈，用来存储‘+’,‘-’, ‘\*’,‘/’ ,‘(’,‘)’,‘\[’, ‘\]’,‘\{’ ,‘\}’等操作符
2.  如果当前运算符优先级('\*/')高于栈顶运算符('+-')优先级，则将运算符入栈；反之，从数字栈中弹出两个数，从运算符栈中弹出栈顶运算符，进行运算，数字栈压入运算结果，符号栈压入当前运算符。重复该操作直到不满足条件。
3.  出现左括号‘(’，则直接压入；出现右括号‘)’，则从数字栈中弹出两个数，从运算符栈中弹出栈顶运算符，进行运算，数字栈压入运算结果，重复该操作直到栈顶元素为左括号‘(’。

难点：

1.  将数字从字符串中提取出来，而且要考虑正负号
2.  运算符有优先级：有括号先算括号里的，再算乘除，最后加减，要满足从左往右运算顺序

注意：由于有除法运算，应该使用double格式来保存计算结果

# 使用到的字符串操作函数 #

## find()与find\_first\_of() ##

<table style="width:600px;"> 
 <tbody> 
  <tr> 
   <th> <p>string (1)</p> </th> 
   <td> <p>size_t find (const string&amp; str, size_t pos = 0) const noexcept;</p> </td> 
  </tr> 
  <tr> 
   <th> <p>c-string (2)</p> </th> 
   <td> <p>size_t find (const char* s, size_t pos = 0) const;</p> </td> 
  </tr> 
  <tr> 
   <th> <p>buffer (3)</p> </th> 
   <td> <p>size_t find (const char* s, size_t pos, size_type n) const;</p> </td> 
  </tr> 
  <tr> 
   <th> <p>character (4)</p> </th> 
   <td> <p>size_t find (char c, size_t pos = 0) const noexcept;</p> </td> 
  </tr> 
 </tbody> 
</table>

string s = "hello world!";
    	cout << s.find('o') << endl;//4
    	cout << s.find('o', 5) << endl;//7
    	cout << s.find("world") << endl;//6
    	cout << s.find("word") << endl;//4294967295，未找到
    	cout << s.find_first_of("word") << endl;//4,“wor” 出现在原字符串中，
    	cout << s.find_last_of('o') << endl;//7

在当前字符串s中搜索传入参数字符串或者字符在s中首次出现的下标，与find\_first\_of()不同的是，find\_first\_of()找到了首个匹配的实例之后就不找了，就认定找寻成功，返回首个字符的下标，而find()则是要求完全匹配。如果输入了pos参数，则从下标pos开始查找。

**查找失败：返回string::npos**

static const size_t npos = -1;
    //npos is a static member constant value with the greatest possible value for an element of type size_t.

npos是一个静态成员常量，其值为size\_t类型的最大值：4294967295，用来表示没找到元素。

## substr() ##

截取字符串

string substr (size_t pos = 0, size_t len = npos) const;

第一个参数pos是开始截取的位置下标，第二个参数len是截取的长度 ,若len==npos,意思是截取字符串从pos直到末尾

## stoi()与stod() ##

将字符串转成int类型或double类型

# 实现代码 #

#include<iostream>
    #include<stack>
    #include<string>
    using namespace std;
    string nums = "0123456789";
    //比较函数，用于比较当前操作符和栈顶操作符的优先级
    //如果当前操作符优先级大于栈顶优先级，返回false
    //如果栈顶操作符为左括号(
    //如果当前操作符优先级小于栈顶优先级，true
    //还要满足从左往右计算顺序，如果当前操作符与栈顶操作符为同级关系，返回true
    //返回true说明此时需要将栈顶操作符弹出，用于计算
    bool cmp(char top, char now){
        if(top == '('){
            return false;
        }else if((top == '-' || top == '+') && (now == '*' || now == '/')){
            return false;
        }
        return true;
    }
    //计算，从数字栈中弹出两个数字，操作符栈中弹出操作符
    void calculate(stack<double> &num,stack<char> &op){
    //     数字栈中数字的顺序也有要求
    //     第一个弹出的数字在后面，第二个弹出的在前面
        double b = num.top();
        num.pop();
        double a = num.top();
        num.pop();
        char c = op.top();
        op.pop();
        if(c == '+') a = a+b;
        else if(c == '-') a = a-b;
        else if(c == '*') a = a*b;
        else if(c == '/') a = a/b;
        //将结果放入数字栈
        num.push(a);
        return ;
    }
    int main(void){
        string s;
        while(getline(cin, s)){
            //数字栈
            stack<double> num_stk;
            //操作符栈
            stack<char> op_stk;
            //预处理，将算式用括号括起来
            op_stk.push('(');
            s += ')';
            //算式的第一个应该是数字
            bool isNextOp = false;
            for(int i=0; i<s.size(); ++i){
                //左括号的话，直接压入操作符栈,将大中小括号都当做小括号处理
                if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                    op_stk.push('(');
                }
                //右括号的话就可以开始计算，直到遇到与之对应的左括号
                else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){
                    while(op_stk.top() != '(') //计算
                        calculate(num_stk,op_stk);
                    //弹出此时的（
                    op_stk.pop();
                }
                //除括号外，数字和操作符应该是间隔排列的，而且算式的第一个应该是数字
                //若没有括号，需要考虑操作符优先级问题,并且是从左往右计算
                else if(isNextOp){
                    while(cmp(op_stk.top(),s[i])){
                        //计算
                        calculate(num_stk,op_stk);
                    }
                    op_stk.push(s[i]);
                    isNextOp = false;
                }
                //将数字从字符串中提取出来
                else{
                    int j = i;
                    //+ -符号可能是正负符号
                    if(s[j] == '+' || s[j] == '-') ++i;
                    //数字可能有多位，在0-9中
                    while(nums.find(s[i]) != nums.npos) ++i;
                    //i和j之间的字符即为数字
                    //将数字提取，并压入数字栈
                    
                    //num_stk.push(stod(nums.substr(j,i-j)));
                    num_stk.push((double)stoi(s.substr(j,i-j)));
                    --i;
                    //当前为数字，所以下一个为操作符
                    isNextOp = true;
                }
            }
            //数字栈顶的元素即为最后结果
            cout<<num_stk.top()<<endl;
        }
        return 0;
    }

# 算法动图 #

![20210404234322528.gif][]

![20210404234330971.gif][]

# 算法动图制作方法 #

在网上经常看见别人写的算法图解动图，本以为有专门的软件可以用，但是没有找了一圈并没有发现这种软件。

网上的一些动图开源项目：

> [https://juejin.cn/post/6844903749203263501][https_juejin.cn_post_6844903749203263501]
> 
> [https://github.com/MisterBooo/Play-With-Sort-OC][https_github.com_MisterBooo_Play-With-Sort-OC]

于是自己决定采用土办法，使用PPT+录屏软件来制作算法动图：

发现一个很好用的gif录屏工具：[screentogif][]

> 下载链接：[https://www.screentogif.com/][screentogif]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70][]

首先在PPT中将算法步骤一张一张描绘出来，然后使用gif录屏软件制即可：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1][]

当前算法PPT下载地址：

[图解PPT][PPT]

[20210404234322528.gif]: /images/20221022/b9ff9ab4c4204d24b547951c9e9ef499.png
[20210404234330971.gif]: /images/20221022/691957cb8c6d47ea81462f54ab7520ef.png
[https_juejin.cn_post_6844903749203263501]: https://juejin.cn/post/6844903749203263501
[https_github.com_MisterBooo_Play-With-Sort-OC]: https://github.com/MisterBooo/Play-With-Sort-OC
[screentogif]: https://www.screentogif.com/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70]: /images/20221022/e2e8c808492a4ac6abacb77b7fb9b963.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1]: /images/20221022/3d647124055f4ba08ac0d19224bfa8c5.png
[PPT]: https://download.csdn.net/download/luolaihua2018/16441229?spm=1001.2014.3001.5503