算术表达式求值的难点
运算符有优先规则
对于一般的算术表达式a*b+(c-d/e)*f来说,如果要对它求值,在计算机取到×的时候,不能直接运算,需要继续往后取值,找是否有比×运算级高的符号,没有的话才能运算。
运算符的操作数是否能直接操作
除了运算符优先规则之外,还不能保证运算符的两个操作数都是可以直接操作的,比如针对上式的+来说,它的两个操作数a*b和(c-d/e)f是不能直接操作的,需要进一步计算ab和(c-d/e)*f的值
这些难点导致计算机直接用算术表达式来计算值的不方便,而将算术表达式转换成后缀表达式将解决以上难点
后缀表达式
概念
后缀表达式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。
正是因为没有优先规则,因此可以根据运算符的先后出现顺序来进行计算。
特点
在一般算术表达式中不同运算符优先级高的在后缀表达式中是放在后面的,以a*b+(c-d/e)f为例,它的后缀表达式abcde/-f **+。
用位置前后来表达运算符的优先级,因此不再考虑运算符优先规则。
转换算法
将一般算术表达式转换成后缀表达式。(在这里用字母a, b, c, ……来代替数字,便于判断。如果是数字,那么每次遇到数字,需要将这个数字串输出)
(1) 首先构造一个运算符栈,运算符(以括号为分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。
(2)从左向右扫描算术表达式,从左边第一个字符开始判断:
a.如果当前字符是字母,则直接输出。
b.如果是运算符(不包括括号),则比较优先级。
①如果是空栈,直接入栈;
②如果当前运算符的优先级大于栈顶运算符的优先级,则将运算符直接入栈;
注:对于优先级相同的运算符来说,先出现的先运算,所以优先级相等的情况是要先将栈顶元素出栈再将当前元素入栈。
③否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于栈顶运算符的优先级or栈顶是左括号时,再将当前运算符入栈。
注:括号比任何在括号前面入栈的元素优先级都大,比任何在左括号之后的,右括号之前的优先级都小。因为括号之中的运算符优先级最大
c.如果是括号,则根据括号的方向进行处理。
①如果是左括号,则直接入栈;
②否则,遇右括号前将所有的运算符全部出栈并输出,遇左括号后将左右的两括号一起删除。
(3) 重复上述操作(2)直至扫描结束,将栈内剩余运算符全部出栈并输出。
注:看到这里的逆序输出就明白为什么之前栈内运算符是优先级增加的原则排列了吧。
中缀表达式也就转换为后缀表达式了。
假设不存在非法输出,以’#'为终止符
数据结构实验之栈与队列二:一般算术表达式转换成后缀式
string Swap (string s)
{string temp;Stack operators;operators.Push('#');bool flag = true;for (int i = 0; flag; i++){char t = s[i];//如果是操作符,就和栈顶元素比较,如果优先级高,就入栈,否则将栈顶元素输出,再将该操作符压入栈中//如果是操作数,就直接输出。switch(t){case '(':{operators.Push(t);break;}case ')':{char c = operators.Pop();while (c != '('){temp += c;c = operators.Pop();}break;}case '*':case '/':{//只要栈顶元素不是'*'和'/',就要入栈char c = operators.Pop();while (c == '*' || c == '/'){temp += c;c = operators.Pop();}operators.Push(c);operators.Push(t);break;}case '+':case '-':{//只要栈顶元素不是'('和'#',就要先将栈顶元素出栈char c = operators.Pop();while (c != '(' && c != '#'){temp += c;c = operators.Pop();}operators.Push(c);operators.Push(t);break;}case '#':{//输入结束,将栈中元素统统出栈char c = operators.Pop();while (c != '#'){temp += c;c = operators.Pop();}flag = false;break;}default:{//操作数temp += t;break;}}}return temp;
}
后缀表达式值的计算
使用一个栈s来进行值的计算。
从左向右扫描后缀表达式,遇到操作数压入s栈,遇到运算符,将栈顶的2个元素出栈计算,再将结果压入s栈;直到结束,将栈中唯一的元素出栈。
int Calculation (string s)
{Stack stack;for (int i = 0; s[i] != '#'; i++){if (s[i] >= '0' && s[i] <= '9'){stack.Push((int)(s[i] -48));continue;}else{int a, b;a = stack.Pop();b = stack.Pop();if (s[i] == '+')stack.Push(a+b);else if (s[i] == '-')stack.Push(b-a);else if (s[i] == '*')stack.Push(b*a);else if (s[i] == '/')stack.Push(b/a);}}return stack.Pop();
}
数据结构实验之栈与队列三:后缀式求值
前缀表达式
概念
前缀表达式是一种没有括号的算术表达式,其将运算符写在前面,操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz,前缀表达式也称为“波兰式”。
对于一般的算术表达式
ab+(c-d/e)f,它的前缀表达式是:+ab-c/def
(a+b)(c+d),它的前缀表达式是:+ab+cd
a+b,它的前缀表达式是:+,a,b
a+(b-c),它的前缀表达式是:+,a,-,b,c
a+(b-c)d ,它的前缀表达式是:+,a,,-,b,c,d
a+1+3 ,它的前缀表达式是: +,+,a,1,3
特点
可以看出在一般算术表达式中不同运算符优先级高的在前缀表达式中是放在后面的,以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 × /这种优先级相同的运算符的处理。
在前缀表达式的转换中,遇到运算符优先级相等的情况是入栈的。
在后缀表达式的转换中,遇到运算符优先级相等的情况是出栈的。
原因在于,后缀表达式是从左向右扫描的,在优先级相同的时候,是先进栈的运算符先运算;而前缀表达式是从右向左扫描的,在优先级相同的时候,是后进栈的运算符先运算。所以,在运算符栈中的操作,对于后缀表达式来说,只要不大于栈顶元素,就要将栈顶元素出栈,而前缀表达式是不大于等于栈顶元素,才将栈顶元素出栈。
可以看到前缀和后缀表达式在求表达式值的时候比一般表达式方便的多
中缀表达式
概念
运算符在操作数之间
与一般算术表达式有区别,中缀表达式无法正确还原一般算术表达式,依旧以ab+(c-d/e)f为例,中缀表达式ab+c-d/ef










