1.算法描述
例如a+b*c这是常见的中缀表达式,但是为了方便计算,在计算机中常要转换为后缀表达式abc*+的形式,那
如何转换呢?
用到的关键数据结构:栈
转换的关键原则:
1.优先级判断:关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*
/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式中*出现在+前面,
2.操作数处理:遇到操作数的时候总是直接输出,不做任何比较
3.括号处理:遇到左括号总是直接入栈,遇到右括号的时候总是弹栈,一直弹到遇到一个左括号
4.优先级处理:遇到操作符的时候就先将这个操作符和它前面的操作符比较优先级
a.高于前面(栈顶)的优先级,先将它压栈;
b.低于或等于前面的操作符的优先级,就把前面的优先级比它高的或相等的顺序弹出来, 一直弹到遇到优先级比它还低的或者到了栈顶,然后在压栈.
2.优先级
enum{FLAG = -1, // FLAG为栈顶标志,优先级最低,这样做的目的在于任何操作符都能够压栈(4.优先级处理中有说明)
L_BRCAKET = 0, // 次与上面,目的在于所有操作符都能在(之后压栈(3.括号处理)
PLUS = 1, //然后其他就按常规规定
MINUS = 1,
MULTIPLY = 2,
DIVISON = 2,
PERSENT = 2,
POWER = 2};
分别为左括号,加减乘除的优先级定义,这儿有一个 FLAG = -1.是做什么咧?
假如分析上面的4点就会发现,有一些特例,比如第一个操作符入栈之前要跟前面的操作符比较优先级,
但是前面还没有操作符,就只好当做一个特例特别处理,先判断是否栈为空,然后操作, 假如我们先将 一个标志符号压入栈,
并让它的优先级低于其他所有的操作符的优先级,这样它就永远不会被弹出, 而且消除了特例的判断,这是技巧
另外注意,把左括号的优先级定义的很低,这也是有道理的.因为我们总是当遇到右括号的时候才把左括号弹出来..
3.判断伪代码:
for(遍历所有字符){
if(数字) 输出;
else{
if(左括号) 入栈;
else if(右括号) 弹栈,一直弹到遇到一个左括号;
else{
判断操作符优先级;
if(栈顶优先级小于当前优先级){
压栈;
}else{
将小于当前优先级的所有操作符出栈,然后入栈;
}
}
}
}
4.代码
#include <iostream>
#include "stack.h"
#include <cstring>
using namespace std;
//定义操作符优先级
enum{ FLAG = -1, // FLAG为栈顶标志,优先级最低,此时根据规则,则所有操作符都可以入栈
L_BRACKET = 0, //左括号优先级最低
PLUS = 1,
MINUS = 1,
MULTIPLY = 2,
DIVISON = 2,
PERSENT = 2,
POWER = 2;
};
//获取操作符优先级
int getPri(char ch){
switch(ch){
case '+':
return PLUS;
case '-':
return MINUS;
case '*':
return MULTIPLY;
case '/':
return DIVISON;
case '%':
return PERSENT;
case '^':
return POWER;
case '(':
return L_BRACKET;
case '#':
return FLAG;
}
}
//判断是否是操作符
bool isOper(char ch){
if((ch == '+') || (ch == '-') || (ch == '*') || (ch == '/') || (ch == '%') || (ch == '^'))
return true;
return false;
}
//判断是否是括号
bool isBracket(char ch){
if(ch == '(' || ch == ')')
return true;
else
return false;
}
int main(){
//string infix = "10/(2+3)"; (1+2)/2+(3+5)*7; "2*3/5-(2*3)"
string infix = "(1+2+3)/2/3+(3+5)*7";
cout<<"中缀表达式:"<<infix<<endl;
stack<char> opt; //栈
opt.push('#'); //#作为栈底结束
int len = infix.length();
int flag = 0; //记录结果
char* result = new char[len]; //存储结果
for (int i = 0; i < len; i++)
{
char ch = infix.at(i);
//1.判断是否是操作数,如果是则直接打印,否则继续判断
if(!isOper(ch) && !isBracket(ch)){
result[flag++] = ch;
}
//2.如果是操作符,则判断是哪种类型,若是(则直接入栈,其他判断优先级决定出入栈
else{
if(ch == '('){ //a.(则入栈
opt.push(ch);
}else if(ch == ')'){ //b.如果是)则,全部出栈,直到遇到(
while(opt.top() != '('){
result[flag++] = opt.pop();
}
opt.pop(); //最后一个'('出栈
}else{ //c.判断操作符+,-,*,/...
char t = opt.top(); //首先,看当前栈顶是什么操作符
int pre = getPri(t);
int cur = getPri(ch);
//A.操作符比较规则1:高于栈顶的优先级,先将它压栈
//(这里用了一个技巧,当栈为空此时栈底是'#'优先级最低-1,其次是'('为0,这样所有操作符此种情况都可入栈)
if(cur > pre){
opt.push(ch);
}
//B.操作符比较规则2:小于等于栈顶的优先级,把前面的优先级比它高的或相等的顺序弹出来, 一直弹到遇到优先级比它还低的或者到了栈顶,然后在压栈
else{
result[flag++] = opt.pop();
pre = getPri(opt.top());
while(pre >= cur){
result[flag++] = opt.pop();
pre = getPri(opt.top());
}
opt.push(ch); //最后不要忘记将当前(优先级相同)的ch压栈
}
}
}
}
char ch = opt.top(); // 表达式扫描完后把栈中剩余的操作符全部输出
while (ch != '#')
{
result[flag++] = ch;
opt.pop();
ch = opt.top();
}
//输出结果
cout<<"后缀表达式:";
for(int i=0; i<flag; i++){
cout<<result[i];
}
cout<<endl;
delete[] result;
return 0;
}
5.
注1:栈stack.h和后缀表达式的计算见http://hao3100590.iteye.com/blog/1569122
谢谢!
分享到:
相关推荐
中缀表达式转换为后缀表达式,用堆栈实现!!!!!!!!
自定义栈,中缀表达式转换为后缀表达式并求值,三个抽象数据类型定义(1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value)
这是一个基于栈实现的中缀表达式转换为后缀表达式的C++程序代码 支持+,-,*,/,%,(),代码仅供参考,有什么问题欢迎指出==
中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素...
用二叉树实现中缀表达式转换成后缀表达式,内含一个CPP文件的代码和一个截图,很不错的,是我自己写的。
该程序实现了运算表达式转换为中缀表达式、中缀表达式转换为后缀表达式及后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
将中缀表达式转换为后缀表达式_C++程序
栈的应用 括号匹配 计算后缀表达式的值 中缀表达式转换为后缀表达式
将中缀表达式转换为后缀表达式是一种常见的数学计算问题,通常使用栈来实现。下面是将中缀表达式转换为后缀表达式的一般步骤: 创建一个空栈,用于存储运算符和临时结果。 创建一个空列表,用于存储后缀表达式。
本程序是java堆栈的应用,实现中缀表达式转换成后缀表达式以及结果计算。
将中缀表达式转换为后缀表达式.c
用户输入中缀表达式,程序输出后缀表达式并输出计算结果
中缀表达式转换为后缀表达式的一般算法.docx
基本思路是:设中缀表达式的字符串为s1,用来存放后缀表达式的字符串为s2,从头到尾扫描中缀表达式中的每个字符,若是空格则不做任何处理,若是数字或者小数点,这直接写入s2中,并在每个数字的最后写入一个空格,如遇到的是...
将中缀表达式转换为后缀表达式并计算.doc
可以实现将一个以#号结束的中缀表达式转换为后缀表达式
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要省略,不影响原计算顺序的括号要...
数据结构-3期(KC002) 中缀表达式转换为后缀表达式设计.docx 学习资料 复习资料 教学资源
使用键盘输入表达式,计算表达式的值并输出;将表达式转化成后缀表达式输出,利用后缀表达式求表达式的值并输出。
C++栈实现将中缀表达式转换为后缀表达式借鉴.pdf