C++表达式求值与转换（前缀、中缀、后缀） |
您所在的位置：网站首页 › 求前缀表达式 › C++表达式求值与转换（前缀、中缀、后缀） |
|
一、前言
最近复习到数据结构的栈和队列的应用部分，学习了一下王道视频里表达式求值部分的思路，特地写了下代码跟大家分享，仅供学习参考。若有错误的地方，请多指教！😄😄😄 二、目录1、中缀表达式转前缀表达式 2、中缀表达式转后缀表达式 3、前缀表达式求值 4、后缀表达式求值 5、中缀表达式求值 三、正文 1、中缀表达式转前缀表达式建议先看中缀表达式转后缀表达式，比较好理解一些。 思路1、从右往左扫描中缀表达式，直到最后一个元素为止： 如果遇到操作数。则直接加入前缀表达式。如果遇到运算符。则比较当前运算符和栈顶符号的优先级。 如果当前运算符的优先级大于栈顶符号的优先级，则直接将该运算符压入栈中；否则，依次弹出栈中所有优先级大于等于当前运算符的所有运算符，并加入到前缀表达式。最后把当前运算符压入栈中。 如果遇到界限符。 遇到右括号“)”，则直接将右括号压入栈中；遇到左括号“(”，则依次弹出栈内运算符并加入前缀表达式，直到弹出右括号“)”为止。注意“)”不加入前缀表达式。2、最后，将栈中剩余的运算符依次弹出，并加入到前缀表达式。注意此时得到的是前缀表达式的逆序，我们需要将结果倒序一下，大功告成！😁😁😁 注意：括号的优先级应该设为最低噢！ 代码 //规定优先级 int level(char s){ if(s=='+' || s=='-') return 1; else if (s=='*'||s=='/') return 2; //设括号优先级为0 else return 0; } //中缀表达式转前缀表达式 char* infix_to_prefix(char *str){ //用栈结构，将字符串倒序，以符合“从右往左”原则。 stack s; int i=0; while(str[i]!='\0'){ s.push(str[i]); ++i; } //定义一个栈来保存结果; stack result; //定义一个栈来作为符号栈 stack symbol_stack; while(!s.empty()){ char temp=s.top(); s.pop(); //--------------数字处理------------------ if(temp>='0'&&temp 符号栈的 栈顶符号的 优先级 if(symbol_stack.empty()||level(temp)> level(symbol_stack.top())){ symbol_stack.push(temp); } //如果扫描到的 运算符的 优先级 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |