今天面试遇到一个题:"中缀表达式转换为后缀表达式"
不知道大家是怎么实现的, 自己回来想了下思路如下:把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。加减运算符的优先级设定为1,乘除运算符的优先级设定为2,在栈中保存的特殊运算符’@’和’(’的优先级设定为01. 若遇到的是空格则认为是分隔符,不需要进行处理;
2. 若遇到的是数字或小数点,则直接写入到s2中,并在每个数值的最后写入一个空格;
3. 若遇到的是左括号,则应把它压入到运算符栈中,待以它开始的括号内的表达式转换完毕后再出栈;
4. 若遇到的是右括号,则表明括号内的中缀表达式已经扫描完毕,把从栈顶直到保存着的对应左括号之间的运算符依次退栈并写入s2串中;
5. 若遇到的是运算符,
5.1 当该运算符的优先级大于栈顶运算符的优先级时,表明该运算符的后一个运算对象还没有被扫描也没有被放入到s2串中,应把它暂存于运算符栈中,待它的后一个运算对象从s1串中读出并写入到s2串中后,再令其出栈并写入s2串中;
5.2 若遇到的运算符的优先级小于或等于栈顶运算符的优先级,这表明栈顶运算符的两个运算对象已经被保存到s2串中,应将栈顶运算符退栈并写入到s2串中,对于新的栈顶运算符仍继续进行比较和处理,直到被处理的运算符的优先级大于栈顶运算符的优先级为止,然后让该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时,把栈中剩余的运算符依次退栈并写入到后缀表达式中,再向s2写入表达式结束符’@’和字符串结束符’{post.abstract}’,整个转换过程就处理完毕,在s2中就得到了转换成的后缀表达式。详细代码见: http://blog.csdn.net/fengsousousou/archive/2008/11/27/3390193.aspx
不知道大家是怎么实现的, 自己回来想了下思路如下:把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。加减运算符的优先级设定为1,乘除运算符的优先级设定为2,在栈中保存的特殊运算符’@’和’(’的优先级设定为01. 若遇到的是空格则认为是分隔符,不需要进行处理;
2. 若遇到的是数字或小数点,则直接写入到s2中,并在每个数值的最后写入一个空格;
3. 若遇到的是左括号,则应把它压入到运算符栈中,待以它开始的括号内的表达式转换完毕后再出栈;
4. 若遇到的是右括号,则表明括号内的中缀表达式已经扫描完毕,把从栈顶直到保存着的对应左括号之间的运算符依次退栈并写入s2串中;
5. 若遇到的是运算符,
5.1 当该运算符的优先级大于栈顶运算符的优先级时,表明该运算符的后一个运算对象还没有被扫描也没有被放入到s2串中,应把它暂存于运算符栈中,待它的后一个运算对象从s1串中读出并写入到s2串中后,再令其出栈并写入s2串中;
5.2 若遇到的运算符的优先级小于或等于栈顶运算符的优先级,这表明栈顶运算符的两个运算对象已经被保存到s2串中,应将栈顶运算符退栈并写入到s2串中,对于新的栈顶运算符仍继续进行比较和处理,直到被处理的运算符的优先级大于栈顶运算符的优先级为止,然后让该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时,把栈中剩余的运算符依次退栈并写入到后缀表达式中,再向s2写入表达式结束符’@’和字符串结束符’{post.abstract}’,整个转换过程就处理完毕,在s2中就得到了转换成的后缀表达式。详细代码见: http://blog.csdn.net/fengsousousou/archive/2008/11/27/3390193.aspx
要模仿表达式,求出结果当时我就把中缀变为后缀做的
比如连这种变态的表达式也能求:
-1-1+(-2)*3-8/2+2*(2-((3+2)*6))+2-(2*2)*(2*2)+(2-2)+2-((((2+2)))+(-9))
做了我300行... 而且做的还是有点BUG 但老师用递归的办法,200行就搞定了....而且条例很清晰