购物券网站怎么做,有哪些营销型网站,管理培训,wordpress 图标不显示缩略图难度参考 难度#xff1a;中等 分类#xff1a;栈与队列 难度与分类由我所参与的培训课程提供#xff0c;但需要注意的是#xff0c;难度与分类仅供参考。且所在课程未提供测试平台#xff0c;故实现代码主要为自行测试的那种#xff0c;以下内容均为个人笔记#xff0c…难度参考 难度中等 分类栈与队列 难度与分类由我所参与的培训课程提供但需要注意的是难度与分类仅供参考。且所在课程未提供测试平台故实现代码主要为自行测试的那种以下内容均为个人笔记旨在督促自己认真学习。
题目 根据逆波兰表示法求表达式的值。 有效的运算符包括·*/。每个运算对像可以是整数也可以是另一个逆波兰表达式。 说明 整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数 为0的情况。 示例1: 输入[213*门 输出9 解释该算式转化为常见的中缀算术表达式为(21)*3)9 示例2: 输入[4135/门 输出6 解释该算式转化为常见的中缀算术表达式为(4(13/5)6
思路 逆波兰表达式求解的一般思路是使用栈来存储操作数然后遍历逆波兰表达式的每个元素根据遇到的操作符进行相应的计算并将结果重新入栈。遍历逆波兰表达式并根据运算符进行相应的计算操作。 具体步骤如下
定义一个栈用于存储中间结果。遍历逆波兰表达式对于每个元素 如果是数字则将其转换为整数并压入栈中。如果是运算符则从栈中取出两个数字进行相应的运算。将运算结果压入栈中。遍历结束后栈中存储的元素即为表达式的最终结果。
示例 逆波兰表达式是一种不需要括号的数学表达式表示法操作符位于操作数之后。 主要思路是使用一个栈来存储操作数并依次遍历输入的表达式。当遇到操作符时从栈中弹出对应数量的操作数并根据操作符进行相应的运算将运算结果压入栈中。当遍历完整个表达式后栈中只会剩下一个元素即表达式的最终结果。 举个例子来说明假设我们要求解的逆波兰表达式是2 1 3 *。我们依次遍历表达式中的每个字符
第一个字符 “2” 是一个操作数我们直接将其压入栈中 2, 1, , 3, * //字符^st{2} //数字 第二个字符 “1” 是另一个操作数同样将其压入栈中 2, 1, , 3, * //字符^st{2, 1} //数字 第三个字符 “” 是一个加法操作符此时栈中的顶部两个元素分别是 1 和 2我们将它们弹出并做加法运算得到 3将结果 3 压入栈中 2, 1, , 3, * //字符^st{3} //数字 第四个字符 “3” 是一个操作数将其压入栈中 2, 1, , 3, * //字符^st{3, 3} //数字 最后一个字符 “*” 是一个乘法操作符此时栈中的顶部两个元素分别是 3 和 3弹出并做乘法运算得到 9将结果 9 压入栈中。 2, 1, , 3, * //字符^st{9} //数字 最终栈中只剩下一个元素 9即为表达式的结果。
梳理 根据逆波兰表达式的性质每当遇到一个操作符时它前面的两个操作数已经被处理过并保存在栈中。所以我们只需要从栈中弹出这两个操作数根据操作符进行相应的运算并将结果再次压入栈中。
没有括号逆波兰表达式的特点是不需要括号来标识优先级因为操作数和操作符的顺序已经明确不存在歧义。简化运算符的处理由于操作符总是位于操作数之后栈可以很方便地保存操作数。每当遇到一个操作符只需要从栈中弹出所需的操作数进行运算而不需要关心操作数之间的顺序或优先级。遍历一次求解由于逆波兰表达式的特点我们只需要遍历一次表达式即可求解无需进行多次迭代或递归。 总体来说通过利用栈的先入后出LIFO的特性将逆波兰表达式转化为了一种线性的、遍历一次即可求解的算法从而实现了逆波兰表达式的求值。 代码
#include iostream // 包含输入输出流库用于标准输入输出
#include stack // 包含栈库用于存储操作数
#include vector // 包含向量库用于存储输入的逆波兰表达式
#include string // 包含字符串库用于操作字符串
#include cstdlib // 包含标准库用于字符串转整数的函数using namespace std; // 使用标准命名空间int evalRPN(vectorstring tokens) { // 定义了一个函数用于计算逆波兰表达式的值参数为存储表达式的向量stackint st; // 创建一个整型栈对象用于存储操作数for (string token : tokens) { // 遍历逆波兰表达式的每个元素if (token ) { // 如果当前元素为加号int num2 st.top(); // 取出栈顶元素作为第二个操作数st.pop(); // 弹出栈顶元素int num1 st.top(); // 取出新的栈顶元素作为第一个操作数st.pop(); // 弹出栈顶元素st.push(num1 num2); // 将计算结果入栈} else if (token -) { // 如果当前元素为减号逻辑同上int num2 st.top();st.pop();int num1 st.top();st.pop();st.push(num1 - num2);} else if (token *) { // 如果当前元素为乘号逻辑同上int num2 st.top();st.pop();int num1 st.top();st.pop();st.push(num1 * num2);} else if (token /) { // 如果当前元素为除号逻辑同上int num2 st.top();st.pop();int num1 st.top();st.pop();st.push(num1 / num2);} else { // 如果当前元素为数字st.push(stoi(token)); // 将字符串转换为整数后入栈}}return st.top(); // 返回栈中最终的结果
}int main() { // 主函数vectorstring tokens {2, 1, , 3, *}; // 创建一个存储逆波兰表达式的向量其中元素为字符串int result evalRPN(tokens); // 调用 evalRPN 函数计算表达式的值cout result endl; // 输出计算结果tokens {4, 13, 5, /, }; // 更新逆波兰表达式result evalRPN(tokens); // 调用 evalRPN 函数计算表达式的值cout result endl; // 输出计算结果return 0; // 返回 0表示正常结束程序
}
打卡
