C++加餐课-stack_queue：计算器-逆波兰表达式

1.计算器实现思路•150. 逆波兰表达式求值 - 力扣LeetCode•224. 基本计算器 - 力扣LeetCode•我们日常写的计算表达式都是中缀表达式也就是运算符在中间运算数在两边但是直接读取无法马上进行运算——因为一个计算表达式还涉及运算符优先级问题。如 1-2*(3-4)5中遇到-和*都无法运算因为后面还有括号优先级更高。•所以其中一种实现思路是把中缀表达式转换为后缀表达式也就是说分析计算表达式的优先级将运算数放到前面运算符放到运算数的后面然后我们依次读取后缀表达式遇到运算符就可以进行运算了。后缀表达式也就做逆波兰表达式(Reverse Polish NotationRPN)这种表示法由波兰逻辑学家J·卢卡西维兹于1929年提出后来被广泛应用于计算机科学中。【结论】计算器实现的时候给到任意一个四则运算表达式带括号使用后缀表达式更方便于计算。2.后缀表达式的运算方式后缀表达式因为已经确定好优先级运算方式非常简单就是遇到运算符时取前面的两个运算数进行运算。因为经过中缀转后缀优先级已经确定好了先遇到的运算符一定就是需要先运算的。【具体步骤】建立一个栈存储运算数读取后缀表达式遇到运算数入栈遇到运算符出栈顶的两个数据进行运算。运算后将结果作为一个运算数入栈继续参与下一次的运算。读取表达式结束后最后栈里面的值就是运算结果。class Solution { public: int evalRPN(const vectorstring tokens) { //定义栈 stackint s; //遍历后缀表达式操作数入栈 //for (size_t i 0; i tokens.size(); i) for (auto str : tokens) { //const string str tokens[i]; // 如果str为运算数 if (!( str || - str || * str || / str)) { s.push(stoi(str)); } // 如果str为运算符 else { //取左右运算数 int right s.top(); s.pop(); int left s.top(); s.pop(); //匹配运算符、进行相应运算 switch (str[0]) { case : s.push(left right); break; case -: s.push(left - right); break; case *: s.push(left * right); break; case /: s.push(left / right); break; } } } //遍历完毕返回栈顶元素 return s.top(); } };【课堂演示】示例分析先出栈的最靠近运算符的运算数是右操作数——加、乘不论顺序减、除要论顺序。借助栈来实现——特点后进先出——能取到最靠近运算符的两个运算数。3.中缀表达式转后缀表达式3.1转换思路依次读取计算表达式中的值遇到运算数直接输出。建立一个栈存储运算符利用栈后进先出性质遇到后面运算符出栈里面存的前面运算符进行比较确定优先级。遇到运算符如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高则当前运算符入栈。 因为如果栈里面存储的是前一个运算符当前运算符比前一个优先级高说明前一个不能运算当前运算符也不能运算因为后面可能还有更高优先级的运算符。遇到运算符如果栈不为为空且当前运算符比栈顶运算符优先级低或相等说明栈顶的运算符可以运算了则输出栈顶运算符当前运算符继续走前面遇到运算符的逻辑。如果遇到()则把括号的计算表达式当成一个子表达式跟上思路类似进行递归处理子表达式处理后转换出的后缀表达式加在前面表达式的后面即可。计算表达式或者()中子表达式结束值输出栈中所有运算符。【课堂演示】【中缀表达式转后缀表达式分析】首先不改变所有操作数的相对顺序关键是操作符的顺序要根据它的优先级来排列并且要紧跟着它的两个操作数转换思路【1】依次读取计算表达式中的值遇到运算数直接输出。输出打印出来、或者存到容器内这里由于要实现计算器所以选择存到容器内建立一个栈存储运算符利用栈后进先出性质遇到后面运算符出栈里面存的前面运算符进行比较确定优先级。【2·核心逻辑】遇到运算符如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高则当前运算符入栈。因为如果栈里面存储的是前一个运算符当前运算符比前一个优先级高说明前一个不能运算。同时当前运算符也不能运算因为后面可能还有更高优先级的运算符。遇到运算符如果栈不为空且当前运算符比栈顶运算符优先级低或相等说明栈顶的运算符可以运算了则输出栈顶运算符当前运算符继续走前面遇到运算符的逻辑。【3】如果遇到()则把括号的计算表达式当成一个子表达式跟上思路类似进行递归处理子表达式处理后转换出的后缀表达式加在前面表达式的后面即可。计算表达式或者()中子表达式结束值输出栈中所有运算符。【1】因为操作数的相对顺序不会改变所以可以直接输出。这里也需要借助一个栈实现运算符的优先顺序的调整。l1表示第一个左操作数这里的关键就是看第一个右操作数第二个左操作数到底是先和它左边的操作符结合还是先和它右边的操作符结合。【2】栈为空遇到加号不能直接运算因为后面可能有比加号优先级更高的运算符。所以只能先把加号放到栈里面存起来。栈顶存储的是前一个运算符后一个运算符优先级更高则前一个运算符不可以运算后一个也不能直接运算。后一个运算符入栈成为新的“前一个运算符”继续看新的“后一个运算符”后一个运算符优先级不更高则前一个运算符可以运算直接输出。后一个运算符入栈成为新的“前一个运算符”继续看新的“后一个运算符”需要继续走遇到运算符的逻辑栈为空才能入栈。后一个运算符优先级不更高相等或更低则前一个运算符可以运算直接输出哪怕后面还有更高优先级的运算符也不用管。因为运算符是通过相邻的运算符来确定优先级并不会跨着去比较优先级。比如123×4乘号不会影响第一个加号的优先级影响的是第二个加号的优先级。结果1 2 3 4 × 【例1】只有、-【例2】还有*、()【注意】遇到(建立一个新栈递归处理。遇到)递归结束弹出新栈的所有运算符新栈销毁看回旧栈。中缀表达式继续向后走。最后一排跳了一个步骤下图是完整步骤。【减号的处理】减号前面是操作数正常运算加号前面是操作符把减号当作“0-”3.2代码实现class Solution { public: //mapchar, int _operatorPrecedence { { , 1 }, { -, 1 }, { *, 2 }, { /, 2 } }; int operatorPrecedence(char ch) { struct opPD { char _op; int _pd; }; static opPD arr[] { {, 1},{-, 1},{*, 2},{/, 2} }; for (auto e : arr) { if (e._op ch) { return e._pd; } } assert(false); return -1; } void toRPN(const string s, size_t i, vectorstring v) { stackchar st; while (i s.size()) { if (isdigit(s[i])) { // 操作数输出 string num; while (i s.size() isdigit(s[i])) { num s[i]; i; } v.push_back(num); } else { if (s[i] () { // 递归⽅式处理括号中的⼦表达式 i; toRPN(s, i, v); } else if (s[i] )) { i; // 栈中的运算符全部输出 while (!st.empty()) { v.push_back(string(1, st.top())); st.pop(); } // 结束递归 return; } else { // 运算符 // 1、如果栈为空或者栈不为空且当前运算符⽐栈顶运算符优先级⾼则当前运算符⼊栈 // 2、如果栈不为为空且⽐栈顶运算符优先级低或相等说明栈顶的运算符可以运算了 // 输出栈顶运算符当前运算符继续⾛前⾯遇到运算符的逻辑 if (st.empty() || operatorPrecedence(s[i]) operatorPrecedence(st.top())) { st.push(s[i]); i; } else { v.push_back(string(1, st.top())); st.pop(); } } } } // 栈中的运算符全部输出 while (!st.empty()) { v.push_back(string(1, st.top())); st.pop(); } } }; int main() { size_t i 0; vectorstring v; //string str 12-3; string str 12-(3*45)-7; Solution().toRPN(str, i, v); for (auto e : v) { cout e ; } cout endl; return 0; }【课堂演示】计算器的实现拿到的参数是一个字符串表达式逆波兰表达式的计算拿到的是一个字符串数组。所以“中缀转后缀函数”的参数就需要string接收计算器接收到的表达式const stringvextorstring给到后缀表达式计算函数vectorstring输出型参数size_t i遍历中缀表达式的下标遇到括号进行递归里面i外面也会跟着走。把每个字符输出成一个字符串存储到vectorstring是为了跟前面的接口契合。【注意】多位数就只能用string存储所以才必须使用vectorstring。基本框架string里面包含了cctype。是操作数则直接输出。问题在于可能后一个字符也是操作数——它们一起组成一个多位操作数。操作数不一定是只有个位可能是一个多位数。所以遇到操作数不能直接插入vectorstring需要先存储到一个临时string。往后遍历遇到连续操作数就都尾插给string直到不是操作数再把string输出。遇到运算符就需要借助辅助栈。问题在于运算符的优先级不能使用比较运算符来判定。四则运算符的ASCII码值和他们的运算优先级没关联。所以需要建立运算符和优先级之间的关联没学map使用函数判定学了map使用map判定输出运算符的时候不能直接输出char op因为string是没有直接支持使用char构造的。string支持的是使用n个char去构造这里可以push一个op构造的匿名对象。还需要处理括号的问题插入遇到的运算符是括号需要建立新的辅助栈处理子表达式。当i s.size()表达式结束把辅助栈里面的运算符全部输出。【测试1】【测试2】4.计算器实现有了上面两个部分的基础实现一个计算器的OJ题的大部分问题就解决了。但是这里还有一些问题需要处理OJ中给的中缀表达式是字符串字符串中包含空格需要去掉空格。其次就是负数和减号要进行区分将所有的负数-x转换为0-x。class Solution { public: //mapchar, int _operatorPrecedence { { , 1 }, { -, 1 }, { *, 2 }, { /, 2 } }; int operatorPrecedence(char ch) { struct opPD { char _op; int _pd; }; static opPD arr[] { {, 1},{-, 1},{*, 2},{/, 2} }; for (auto e : arr) { if (e._op ch) { return e._pd; } } assert(false); return -1; } void toRPN(const string s, size_t i, vectorstring v) { stackchar st; while (i s.size()) { if (isdigit(s[i])) { // 运算数输出 string num; while (i s.size() isdigit(s[i])) { num s[i]; i; } v.push_back(num); } else { if (s[i] () { // 递归⽅式处理括号中的⼦表达式 i; toRPN(s, i, v); } else if (s[i] )) { i; // 栈中的运算符全部输出 while (!st.empty()) { v.push_back(string(1, st.top())); st.pop(); } // 结束递归 return; } else { // 运算符 // 1、如果栈为空或者栈不为空且当前运算符⽐栈顶运算符优先级⾼则当前运算符⼊栈 // 2、如果栈不为为空且⽐栈顶运算符优先级低或相等说明栈顶的运算符可以运算了 // 输出栈顶运算符当前运算符继续⾛前⾯遇到运算符的逻辑 if (st.empty() || operatorPrecedence(s[i]) operatorPrecedence(st.top())) { st.push(s[i]); i; } else { v.push_back(string(1, st.top())); st.pop(); } } } } // 栈中的运算符全部输出 while (!st.empty()) { v.push_back(string(1, st.top())); st.pop(); } } int evalRPN(const vectorstring tokens) { stackint s; for (size_t i 0; i tokens.size(); i) { const string str tokens[i]; // str为数字 if (!( str || - str || * str || / str)) { s.push(stoi(str)); } else { // str为操作符 int right s.top(); s.pop(); int left s.top(); s.pop(); switch (str[0]) { case : s.push(left right); break; case -: s.push(left - right); break; case *: s.push(left * right); break; case /: s.push(left / right); break; } } } return s.top(); } int calculate(string s) { // 1、去除所有空格否则下⾯的⼀些逻辑没办法处理 std::string news; news.reserve(s.size()); for (auto ch : s) { if (ch ! ) news ch; } s.swap(news); news.clear(); // 2、将所有的负数-x转换为0-x for (size_t i 0; i s.size(); i) { if (s[i] - (i 0 || (!isdigit(s[i - 1]) s[i - 1] ! )))) news 0-; else news s[i]; } // 中缀表达式转成后缀表达式 size_t i 0; vectorstring v; toRPN(news, i, v); // 后缀表达式进⾏运算 return evalRPN(v); } };【课堂演示】不能直接给原始的中缀表达式s而是需要给处理过后的中缀表达式news。原始的中缀表达式s转换成处理过后的中缀表达式news需要经过两个处理OJ中给的中缀表达式是字符串字符串中包含空格需要去掉空格。其次就是负数和减号要进行区分将所有的负数-x转换为0-x。去除空格的方式find( )然后erase用原始的中缀表达式s构建一个新的中缀表达式news跳过所有的空格显然方法1的效率太低了这里使用方法2。负号的处理减号前面是操作数负号前面是操作符需要转换成“0-”这里if条件判断的情况不容易想到对于不报测试用例的OJ题就很难做出来。负号前面是右括号那实质上是一个操作数——括号的子表达式当作一个操作数看待那这个符号实际上是减号。【扩展】上面的解法写了一百多行代码其实还有更简洁的代码逻辑。这个题解是针对于只有、-、()这几个操作符没有乘除所以能写得这么简单。那所有的加减运算都是平级不会有优先级的问题需要做的就是去除括号。加号后面的括号直接去除括号减号后面的括号将括号内部的所有符号变号然后去除括号如果还有乘除号也可以采用去除括号的思路加号后面的括号直接去掉减号后面的括号需要先把括号内的加减号变号再去掉括号。嵌套的括号就需要一些标记来记录变号的情况。去除完括号得到new_s表达式。有乘除号的表达式还是有优先级的问题不转后缀表达式的话可以先遍历一遍表达式先把乘除法运算了得到new_new_s表达式。最后只剩加减再依次计算就可以了。这个题就是没有括号但是有加减乘除。这就是不用后缀表达式的计算器的另一种实现方式先去除括号变号再优先计算乘除。实现后缀表达式的计算器意义在于这是很多数据结构教科书里面的标准解法同时练习了对于栈这个数据结构的使用。