逆波兰表达式的算法

逆波兰表达式的算法

1、输入一个字符串，将其格式化的储存在一个数组中，以方便的记录表达式中数和各个符号的出现顺序

约定在数组中记录时，每个数或符号用两个整数来记录

第一个整数记录该位是什么东西，0表示是一个数，1表示是括号，2表示反括号，3、4、5、6分别表示乘除加减号

如果该位是一个数，那么第二个整数记录着个数的具体取值，否则记录该位的符号的ASCII码

比如字符串(1-23)会被转化成二位数组{{1,'('},{0,1},{6,'-'},{0,23},{2,')'}}

这个转化过程每什么技巧性，对原字符串各位顺次判断并处理即可

原先的字符串中可能出现一元运算符正号'+'和负号'-'，为了处理方便，一律在其前面加个0，改写成0+...或者0-...

另外为了之后转化逆波兰表达式方便，处理过程中会在转化出的数组的首尾一律添加一对括号

2、将之前所提到的格式数组转化为逆波兰表达式

约定依然用二位数组记录一个逆波兰表达式，并且格式与之前的数组相同，除了没有括号以外

比如逆波兰表达式12-35+，会被记录成{{0,1},{0,2},{6,'-'},{0,35},{5,+}}

转化时需要用一个栈

具体转化操作如下：

顺次处理格式数组的每一位，对其作判断

如果该位是一个数或者是括号'('，，将其入栈

如果该位是乘号'*'或者除号'/'，不断进行出栈操作直到栈顶元素是个括号'('或者加号'+'或者减号'-'，然后将这个乘号或者除号入栈

如果该位是加号'+'或者减号'-'，不断进行出栈操作直到栈顶元素是个括号'('，然后将这个加号或者减号入栈

如果该位是反括号')'，那么不断进行出栈操作直到有一个括号'('出栈

在上述操作中，所有的出栈元素，除了括号'('以外，都被顺次添加到所要生成的逆波兰表达式的末尾

这样就转化出了一条逆波兰表达式

3、对逆波兰表达式求值

求值时也需要用到一个栈

求值步骤如下：

顺次处理逆波兰表达式的每一位，对其作判断

如果该位是一个数，将这个数入栈

如果该位是一个运算符，那么连续进行两次出栈操作，可以得到栈顶的两个元素，对这两个元素用该位的运算符做运算，将所得的结果入栈

比如如果当时栈顶元素是3，次栈顶的元素是2，运算符是减号'-'，那么连续两次出栈得到3和2两个元素，再将2-3的运算结果1入栈

注意有些运算符(减号和除号)不符合交换律，因此运算时必须是次栈顶元素在前、栈顶元素在后，顺序不能反

当每一位都处理完了之后，只要输入的是一个合法的逆波兰表达式，必然栈中只剩下一个元素，这个元素就是逆波兰表达式求值的结果