前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算(栈项元素和次顶元素)，并将结果入栈;重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如: (3+4)X5-6 对应的前缀表达式就是
- X + 3 4 5 6
,针对前缀表达式求值步骤如下:
- 从右至左扫描，将6、5、4、3压入堆栈;
-
遇到+运算符，因此弹出3和4 (3为栈项元素，4为次顶元素)，计算出3+4的值，得7,
再将7入栈
- 接下来是X运算符，因此弹出7和5，计算出7X5-35，将35入栈
- 最后是-运算符，计算出35-6的值，即29， 由此得出最终结果
中缀表达式的计算机求值
中缀表达式就是常见的运算表达式，如(3+4)X5-6
中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)
后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算(次项元素和栈顶元素)，并将结果入栈;重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如: (3+4)X5-6对应的前缀表达式就是3 4+5 X 6-,针对后缀表达式求值步骤如下:
- 从左至右扫描， 将3和4压入堆栈;，
- 遇到+运算符， 因此弹出 4 和 3 (4为栈顶元素，3为次顶元素)，计算出 3+4 的值，得7，再将7入栈;
- 将5入栈;
- 接下来是X运算符，因此弹出 5 和 7，计算出7X5=35，将35入栈; .
- 将6入栈;
- 最后是-运算符，计算出35-6的值， 即29， 由此得出最终结果
使用栈实现逆波兰表达式
在这里需要使用到俩个方法，一个是用于将表达式放入到ArrayList数组当中，方便变量，另一个是进行运算。
放入数组的方法
// 将表达式的数据放入ArrayList当中
public static List<String> getListString(String expression) {
// 把表达式进行分割,按空格
String[] a = expression.split(" ");
List<String> list = new ArrayList<String>();
// 把分割后的数组a放入list
for (String ele : a) {
list.add(ele);
}
return list;
}
数据运算的方法
public static int Calculation(List<String> ls) {
//创建一个栈
Stack<String> stack=new Stack<String>();
//遍历List
for(String item:ls) {
//使用正则表达式判断是不是数
if (item.matches("\\d+")) {//匹配多位数
//直接入栈
stack.push(item);
}else {
//弹出俩个数进行运算再入栈
int num2 =Integer.parseInt(stack.pop());
int num1 =Integer.parseInt(stack.pop());
int res=0;
//判断取出来的运算符符号
if (item.equals("+")) {
res =num1+num2;
}else if(item.equals("-")) {
res =num1-num2;
}else if(item.equals("*")) {
res =num1*num2;
}else if(item.equals("/")) {
res =num1/num2;
}else {
throw new RuntimeException("表达式异常");
}
//把res值入栈,注意数据类型
stack.push(res+"");
}
}
//最后留在栈当中的数据就是结果
return Integer.parseInt(stack.pop());
}
最后调用这俩个方法直接测试
在上面的代码当中是直接给出后缀表达式，但是这存在一个问题，后缀表达式不方便让人理解这是就需要使用到中缀表达式转后缀表达式
中缀表达式转后缀表达式
后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。
具体步骤如下:
- 初始化两个栈:运算符栈s1和储存中间结果的栈s2;.
- 从左至右扫描中缀表达式;
- 遇到操作数时，将其压s2;
- 遇到运算符时，比较其与s1栈项运算符的优先级:
- 如果s1为空，或栈顶运算符为左括号“(”， 则直接将此运算符入栈;
- 否则，若优先级比栈顶运算符的高，也将运算符压入s1;
- 否则，将s1栈项的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较;
- 遇到括号时:
- 如果是左括号“(”，则直接压入s1
- 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
- 重复步骤2至5，直到表达式的最右边
- 将s1 中剩余的运算符依次弹出并压入s2
- 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
示例：
1+（（2+3）*4）-5
所对应的后缀表达式为
1 2 3 + 4 * + 5 -
将中缀表达式转换到list当中
public static List<String> Transformation(String s) {
List<String> ls = new ArrayList<String>();
int i = 0;// 索引,用于遍历中缀表达式字符串
String str;// 多位数的拼接
char c; // 每遍历一个字符就将其放入到c中
do {
// 如果c是一个非数字，加入到ls
if ((c = s.charAt(i)) < 48 || ((c = s.charAt(i)) > 57)) {
ls.add(c + "");
i++;
} else {// 考虑多位数
str = "";
//当现在的这个索引还没有遍历到最后，以及这个字符是一个数字。
while (i < s.length() && ((c = s.charAt(i)) >= 48 && ((c = s.charAt(i)) <= 57))) {
str += c;
i++;
}
ls.add(str);
}
} while (i < s.length());
return ls;
}
定义一个Operration类，定义一个方法用于返回运算符优先级
class Operration {
private final static int ADD = 1;
private final static int SUB = 1;
private final static int MUL = 2;
private final static int DIV = 2;
// 使用对应方法,返回对应的优先级
public static int getValue(String oper) {
int res = 0;
switch (oper) {
case "+":
res = ADD;
break;
case "-":
res = SUB;
break;
case "*":
res = MUL;
break;
case "/":
res = DIV;
break;
default:
System.out.println("符号有误");
break;
}
return res;
}
}
对转换过来的后缀表达式进行运算处理
public static List<String> TransformationList(List<String> ls) {
// 初始化栈
Stack<String> s1 = new Stack<String>();
// s2这个栈没有出栈操作，使用ArrayList代替。
List<String> s2 = new ArrayList<String>();
// 遍历ls
for (String item : ls) {
// 是一个数入s2栈
if (item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
// 右括号,则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃
while (!s1.peek().equals("(")) {
// 当没有找到对应的左括号,一直将数据弹出添加
s2.add(s1.pop());
}
s1.pop(); // 将左括号弹出消除
} else {
// 当 item 的优先级小于等于栈顶符号的优先级
while (s1.size() != 0 && Operration.getValue(s1.peek()) >= Operration.getValue(item)) {
s2.add(s1.pop());
}
//将item压入回s1栈
s1.push(item);
}
}
//把s1中的剩下的运算符全部加入到s2中
while (s1.size()!=0) {
s2.add(s1.pop());
}
return s2;
}
最后再定义一个中缀表达式进行测试
