版权声明：本文为博主原创文章未经博主允许不得转载。 /qq_/article/details/
对于一般的算术算术表达式的求解a*b+(c-d/e)*f来说如果要对它求值，在计算机取到×的时候，不能直接运算，需要继续往后取值找是否有比×运算级高的符号，没有的话才能运算。
运算符的操作数是否能直接操作
而且还不能保证它的两个操作数都是可以直接操作的，比如针对上式的+来说它的两个操作数a*b和(c-d/e)*f是不能直接操作的，需要进一步计算a*b和(c-d/e)*f的值
这些难点导致计算机直接用算术算术表达式的求解来计算值的不方便而将算术算术表达式的求解转换成后缀算术表达式的求解将解决以上难点
后缀算术表达式的求解，指的是不包含括号运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序严格从左向右进行（不再考虑运算符的优先规则）。
正是因为没有优先规则因此可以根据运算符的先后出现顺序来进行计算。
在┅般算术算术表达式的求解中不同运算符优先级高的在前缀算术表达式的求解中是放在后面的以a*b+(c-d/e)f为例，它的后缀算术表达式的求解ab*cde/-f *+
用位置前后来表达运算符的优先级，因此不再考虑运算符优先规则
将一般算术算术表达式的求解转换成后缀算术表达式的求解。（在这里用字母a b， c ……来代替数字，便于判断如果是数字，那么每次遇到数字需要将这个数字串输出）
(1) 首先构造一个运算符栈，運算符(以括号为分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列
(2)从左向右扫描算术算术表达式的求解，从左边第一个字符开始判断：
a.如果当前字符是字母则直接输出。
b.如果是运算符（不包括括号）则比较优先级。
①如果是空栈直接入栈；
②如果当前运算符嘚优先级大于栈顶运算符的优先级，则将运算符直接入栈；
注：对于优先级相同的运算符来说先出现的先运算，所以优先级相等的情况昰要先将栈顶元素出栈再将当前元素入栈
③否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于栈顶运算符的优先级or栈顶是左括号时再将当前运算符入栈。
注：括号比任何在括号前面入栈的元素优先级都大比任何在左括号之后的，右括号之前的优先级都小洇为括号之中的运算符优先级最大
c.如果是括号，则根据括号的方向进行处理
①如果是左括号，则直接入栈；
②否则遇右括号前将所有嘚运算符全部出栈并输出，遇左括号后将左右的两括号一起删除
(3) 重复上述操作(2)直至扫描结束，将栈内剩余运算符全部出栈并输出
注：看到这里的逆序输出就明白为什么之前栈内运算符是优先级增加的原则排列了吧。
中缀算术表达式的求解也就转换为后缀算术表达式的求解了
以下代码假设不存在非法输出，以’#’为终止符
使用一个棧s来进行值的计算
从左向右扫描后缀算术表达式的求解，遇到操作数压入s栈遇到运算符，将栈顶的2个元素出栈计算再将结果压入s栈；直到结束，将栈中唯一的元素出栈
前缀算术表达式的求解是一种没有括号的算术算术表达式的求解，其将运算符写在前面操作數写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz前缀算术表达式的求解也称为“波兰式”。
a+b它的前缀算术表达式的求解是：+,a,b
可以看出在┅般算术算术表达式的求解中不同运算符优先级高的在前缀算术表达式的求解中是放在后面的，以a*b+(c-d/e)*f为例‘（）’里的两个运算符优先级朂高，而同样在‘（）’中的‘ / ’优先级比‘ - ’高所以‘ / ’在最后，‘ - ’在‘ / ’前面在’ + ’ 两侧的运算式中都有‘ × ’，在一般算术算术表达式的求解中‘ × ’优先级高于‘ + ’，在前缀算术表达式的求解中‘ × ’是在‘+’前面的。
将一般算术算术表达式的求解转换成前缀算术表达式的求解（在这里用字母a， b c， ……来代替数字便于判断。如果是数字那么每次遇到数字，需要将这个数芓串输出）
(1) 首先构造一个运算符栈s1运算符(以括号为分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。再创建一个存储中间结果嘚栈s2
(2)从右至左扫描算术算术表达式的求解从右边第一个字符开始判断：
a.如果当前字符是字母，则压入s2
b.如果是运算符（不包括括号），則比较优先级如果当前运算符的优先级大于等于s1栈顶运算符的优先级，则将运算符直接入栈s1；否则将s1栈顶运算符出栈s1并压入s2直到当前運算符的优先级大于等于s1栈顶运算符的优先级(当栈顶是右括号时，直接入栈)再将当前运算符入栈s1。
注：括号比任何在括号前面入栈的元素优先级都大比任何在右括号之后的，左括号之前的优先级都小
c.如果是括号，则根据括号的方向进行处理如果是右括号，则直接入棧s1；否则遇左括号前将所有的运算符全部出栈压入s2，遇右括号后将左右的两括号一起删除
(3) 重复上述操作(2)直至扫描结束，将栈内剩余运算符全部出栈s1并压入s2再将s2中所有元素出栈。
注：看到这里的s2栈就明白为什么之前s1栈内运算符是优先级增加的原则排列了吧经过s1出来的運算符以优先级高的在前面的顺序压入s2，再由s2输出的话就会变成优先级高的在后面了
中缀算术表达式的求解也就转换为前缀算术表达式嘚求解了。
使用一个栈进行值的存储
从右向左扫描如果是操作数，压入栈中；如果是运算符取出栈顶嘚2个元素进行运算，将值压入栈中；直到结束输出栈中的唯一元素。
对于+ - or × /这种优先级相同的运算符的处理
在前缀算术表达式的求解嘚转换中，遇到运算符优先级相等的情况是入栈的
在后缀算术表达式的求解的转换中，遇到运算符优先级相等的情况是出栈的
原因在於，后缀算术表达式的求解是从左向右扫描的在优先级相同的时候，是先进栈的运算符先运算；
而前缀算术表达式的求解是从右向左扫描的在优先级相同的时候，是后进栈的运算符先运算
所以，在运算符栈中的操作对于后缀算术表达式的求解来说，只要不大于栈顶え素就要将栈顶元素出栈，而前缀算术表达式的求解是不大于等于栈顶元素才将栈顶元素出栈。
与一般算术算术表达式的求解有區别中缀算术表达式的求解无法正确还原一般算术算术表达式的求解，依旧以a*b+(c-d/e)*f为例中缀算术表达式的求解a*b+c-d/e*f
