堆栈实现的数学运算表达式计算

电玩女神 2023-06-13 11:06 21阅读 0赞

# 堆栈实现的数学运算表达式计算 #

此处运算表达式为简单数学运算表达式，只包含+，-，\*，/，及（，）  
输入的为一个String字符串  
输入

>  cout << "Input" << endl;
        string a;
        cin >> a;
        MatchedPairs(a);

首先进行括号匹配

> void MatchedPairs(string expr) { 
        linkedStack<int> s;
        //创建一个栈
        int length = (int) expr.size();
        for (int i = 0; i < length; ++i) { 
            if (expr.at(i) == '(')
                s.push(i);//如果遇到左括号，则压进栈中
            else if (expr.at(i) == ')') { 
                //如果遇到右括号则和栈顶元素匹配，一个右括号一定是与离自己最近的左括号进行匹配
                int c = op(expr.substr(s.top() + 1, i - s.top() - 1));
                //将没有括号的字符串送入op函数进行运算并返回
                stringstream ss1;
                ss1 << c;
                string s1 = ss1.str();
                //将int转化为string
                int length2 = (int) s1.size();
                expr.replace(s.top(), i - s.top() + 1, s1);
                //结果替换送去计算的string
                length = length - (i - s.top() + 1) + length2;
                i = i - (i - s.top() + 1) + length2;
                //改变string长度及i
                s.pop();
            }
        }

op函数，没有括号的数学表达式进行运算  
这里需要用到stoi(string)函数  
string str=“154+33”  
int a=stoi(str);  
则a=154;  
stoi()就是用于提取string中符号之前的数字的函数  
但是有些编译器不支持，所以在这里提供一个自己写的

> int sto(string a) { 
        int length = (int) a.size();
        int z = a.at(0) - '0';
        for (int i = 1; i < length; ++i) { 
            if (a.at(i) >= '0' && a.at(i) <= '9') { 
                z = (a.at(i) - '0') + z * 10;
            } else
                break;
        }
        return z;
    }

与stoi()功能相同  
现在来看看op()函数

int op(string str) { 
        int a = sto(str);
        stringstream ss;
        ss << a;
        string str2 = ss.str();
        //先判断是否需要运算，即传入的是不是只是一个数字
        if (str2 == str) { 
            return a;//如是，则直接返回
        }else { 
            linkedStack<int> s;
            int length = (int) str.size();
            linkedStack<int> s2;
            //创建两个栈，一个用于存放运算符，一个用于存放数字
            for (int i = 0; i < length; ++i) { 
                if (str.at(i) == '-') { 
                    if (i == 0 || (str.at(i - 1) < '0' || str.at(i - 1) > '9')) { 
                        int k = -(sto(str.substr(i + 1, length)));
                        s2.push(k);//判断第一个数是不是负数
                    } else { 
                        if (!s.empty()&&s.top()=='-'){ 
                            int i = s2.top();
                            s2.pop();
                            int j = s2.top();
                            s2.pop();
                            s2.push(j-i);
                            s.pop();
                        }//如果之前已经有-存入则先计算
                        s.push('-');//否则存入
                    }
                } else if (str.at(i) == '+') { 
                    if (!s.empty()&&s.top()=='-'){ 
                        int i = s2.top();
                        s2.pop();
                        int j = s2.top();
                        s2.pop();
                        s2.push(j-i);
                        s.pop();
                    }//如果之前已经有-存入则先计算，-的优先级高于+
                    s.push('+');//否则存入
                } else if (str.at(i) >= '0' && str.at(i) <= '9') { 
                    int k = sto(str.substr(i, length));
                    s2.push(k);//将数字存入存入数字栈
                } else if (str.at(i) == '*' || str.at(i) == '/') { 
                    //遇到*或/直接运算后存入
                    int k = sto(str.substr(i + 1, length));
                    int j = s2.top();
                    s2.pop();
                    if (str.at(i) == '*') { 
                        s2.push(k * j);
                    } else { 
                        s2.push(j / k);
                    }
                    i++;
                }
            }
            while (!s.empty()) { 
                //将符号栈中剩余的符号运算完
                int i = s2.top();
                s2.pop();
                int j = s2.top();
                s2.pop();
                cout << "(" << i << "," << j << ")";
                if (s.top() == '-') { 
                    s2.push(j - i);
                    s.pop();
                } else { 
                    s2.push(j + i);
                    s.pop();
                }
            }
            return s2.top();
        }
    }

到此op返回MatchedPairs再返回main，则计算完成。