# 程序员笔记逆波兰表达式计算

//纯数组模拟栈实现(推荐)

class Solution {

public static int evalRPN(String[] tokens) {
int[] numStack = new int[tokens.length / 2 + 1];
int index = 0;
for (String s : tokens) {
switch (s) {
case "+":
numStack[index - 2] += numStack[--index];
break;
case "-":
numStack[index - 2] -= numStack[--index];
break;
case "*":
numStack[index - 2] *= numStack[--index];
break;
case "/":
numStack[index - 2] /= numStack[--index];
break;
default:
// numStack[index++] = Integer.valueOf(s);
//valueOf改为parseInt，减少自动拆箱装箱操作
numStack[index++] = Integer.parseInt(s);
break;
}
}
return numStack[0];
}
}

class Solution {
// 栈实现   8 ms    36.7 MB
public static int evalRPN(String[] tokens) {
Stack<Integer> numStack = new Stack<>();
Integer op1, op2;
for (String s : tokens) {
switch (s) {
case "+":
op2 = numStack.pop();
op1 = numStack.pop();
numStack.push(op1 + op2);
break;
case "-":
op2 = numStack.pop();
op1 = numStack.pop();
numStack.push(op1 - op2);
break;
case "*":
op2 = numStack.pop();
op1 = numStack.pop();
numStack.push(op1 * op2);
break;
case "/":
op2 = numStack.pop();
op1 = numStack.pop();
numStack.push(op1 / op2);
break;
default:
numStack.push(Integer.valueOf(s));
break;
}

## 1120逆波兰中缀转后缀表达式

public static void trans(String s, StringBuilder postexp) {
SequenceStack mystack = new SequenceStack(50);
char temp;
for(int i=0; i<s.toCharArray().length; ) {
switch(s.charAt(i))
{
case '(':    //判定为左括号
mystack.push('(');
i++;
break;
case ')':
temp = (char) mystack.pop();
while(temp != '(') {
postexp.append(temp);
temp = (char) mystack.pop();
}
i++;
break;
case '+':
case '-':
while(!mystack.isEmpty()) {
temp = (char) mystack.getTop();
if(temp != '(') {
postexp.append(temp);
temp = (char) mystack.pop();
}else {
break;
}
}
mystack.push(s.charAt(i));
i++;
break;
case '*':
case '/':
while(!mystack.isEmpty()) {
temp = (char) mystack.getTop();
if(temp=='*' || temp == '/') {
postexp.append(temp);
temp = (char) mystack.pop();
}else {
break;
}
}
mystack.push(s.charAt(i));
i++;
break;

default:
while(s.charAt(i)>='0' && s.charAt(i)<='9') {
postexp.append(s.charAt(i));
i++;
}
postexp.append('#');
break;
}
}

while(!mystack.isEmpty()) {
temp = (char) mystack.pop();
postexp.append(temp);
}
}

public static double compvalue(StringBuilder postexp) {
double a,b,c,d,e = 0;

SequenceStack mystack = new SequenceStack(50);//操作数栈
for(int i=0; i<postexp.length(); i++) {
switch (postexp.charAt(i))
{
case '+':                //判定为'+'号
a = (double) mystack.pop();        //出栈元素a
b = (double) mystack.pop();        //出栈元素b
c=b+a;                //计算c
mystack.push(c);        //将计算结果c进栈
break;
case '-':                //判定为'-'号
a = (double) mystack.pop();        //出栈元素a
b = (double) mystack.pop();        //出栈元素b
c=b-a;                //计算c
mystack.push(c);        //将计算结果c进栈
break;
case '*':                //判定为'*'号
a = (double) mystack.pop();        //出栈元素a
b = (double) mystack.pop();        //出栈元素b
c=b*a;                //计算c
mystack.push(c);        //将计算结果c进栈
break;
case '/':                //判定为'/'号
a = (double) mystack.pop();        //出栈元素a
b = (double) mystack.pop();        //出栈元素b
if (a!=0)
{
c=b/a;            //计算c
mystack.push(c);    //将计算结果c进栈
break;
}
else
{
System.out.println("nt除零错误!n");
System.exit(0);        //异常退出
}
break;
default:                //处理数字字符
d=0;                //将连续的数字字符转换成对应的数值存放到d中
while (postexp.charAt(i)>='0' && postexp.charAt(i)<='9')   //判定为数字字符
{
d=10*d+postexp.charAt(i)-'0';  //将char转成数值型的。
i++;
}
mystack.push(d);        //将数值d进栈

break;
}
}
e = (double) mystack.getTop();
return e;
}

THE END