栈的应用-表达式求值

栈是一种先进后出的数据结构,栈的应用很多,表达式求值问题就是一个典型的应用,包含:括号匹配,中缀/后缀表达式的转换以及后缀表达式求值…

括号匹配

使用栈,可以检查一个表达式的括号是否匹配,由于只关心括号的成对匹配,而不关心括号的类别,所以假设只包含()。

检查括号匹配的算法思路是:

① 依次遍历表达式,记录当前字符
② 如果当前字符不是括号,继续遍历下一个字符
③ 如果当前字符是左括号,入栈
④ 如果单曲字符是右括号,出栈;如果出栈元素是左括号,表示匹配一对括号,如果出栈元素是右括号或者此时栈空,括号不匹配。
⑤ 当表达式遍历完成后,如果栈为空,表示括号匹配,否则不匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static boolean isValidExpression(String expression){
Stack<String> stack=new SeqStack<>();
int exLen=expression.length();
for(int i=0;i<exLen;i++){
char curChar=expression.charAt(i);
switch (curChar){
case '(': //左括号,入栈
stack.push(curChar+"");
break;
case ')': //右括号出栈
if(stack.isEmpty()||!"(".equals(stack.pop())){
return false; //如果栈空或者出栈右括号,不匹配
}
break;
}
}
if(!stack.isEmpty()){ //如果栈不为空,不匹配
return false;
}
return true;
}

中缀表达式转为后缀表达式

表达式可以直接求值运算,平时所写表达式叫做中缀表达式;使用中缀表达式计算必须使用两个栈,一个用来记录操作数,一个用来记录括号。并且中缀表达式会根据括号的优先级导致无法从左向右顺序计算,操作比较繁琐。

后缀表达式:将运算符置于操作数之后的表达式;在后缀表达式中不再有括号。

比如中缀表达式:1+2*(3-4)+5,转为后缀表达式的过程如下图所示:

实现的具体算法如下:
① 遍历中缀表达式,记当前字符为curChar
② 如果curChar是数字,添加到后缀表达式
③ 如果curChar是运算符,将curChar与栈顶运算符比较,如果栈顶运算符优先级不低于curChar的优先级,则出栈加入到后缀表达式,直到栈顶运算符优先级低于curChar。
最后将curChar入栈
④ 如果curChar是左括号,入栈(左括号在栈中的优先级最低)
⑤ 如果curChar是右括号,出栈加入后缀表达式,直到出栈的是左括号
⑥ 表达式遍历完毕后,将栈中剩余的运算符全部依次出栈,加入后缀表达式

为了方便比较各个运算符的优先级,可以事先准备好一个HashMap存储各运算符的优先级:

1
2
3
4
5
6
7
8
9
10
public static Map<String, Integer> getOperatorPriority() {
Map<String, Integer> operatorPriority = new HashMap<>();
operatorPriority.put("(", 0);
operatorPriority.put("+", 1);
operatorPriority.put("-", 1);
operatorPriority.put("*", 2);
operatorPriority.put("/", 2);
operatorPriority.put("^", 3);
return operatorPriority;
}

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static StringBuilder toPostfix(String infix) {
StringBuilder postfix = new StringBuilder();
Stack<String> stack = new SeqStack<>();
Map<String, Integer> operatorPriority = Expression.getOperatorPriority();
int infixLen = infix.length();
for (int i = 0; i < infixLen;) {
char curChar = infix.charAt(i);
switch (curChar) {
case '(':
stack.push(curChar + "");
i++;
break;
case ')':
String top = stack.pop();
while (top != null && !"(".equals(top)) {
postfix.append(top);
top = stack.pop();
}
i++;
break;
case '+':case '-': case '*':case '/':case '^':
while (!stack.isEmpty() && operatorPriority.get(stack.peek()) >= operatorPriority.get(curChar+"")) {
postfix.append(stack.pop());
}
stack.push(curChar + "");
i++;
break;
default: //考虑到多位数字的情况,需要使用一个循环来读取连续的数字字符,并以空格分隔
while (i<infixLen&&(curChar <= '9' && curChar >= '0')) {
postfix.append(curChar + "");
i++;
if(i<infixLen) curChar = infix.charAt(i);
}
postfix.append(" ");
}
}
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix;
}

有一个小细节需要注意,一般建议在循环中对字符串的添加操作使用StringBuilder/StringBuffer,效率会高一些。

后缀表达式求值

终于到了最重要的一步了。

后缀表达式的求值是一种顺序求值,借助一个数字栈,进行操作。

具体算法如下:
① 遍历后缀表达式,记录当前字符为curChar
② 如果curChar为数字,入栈
③ 如果curChar为运算符,则出栈两个数,进行运算,运算结果再入栈

需要注意的是: 由于可能出现123这样的多位数字,而存储是以字符为单位的,所以如果curChar是数字的话,需要将后面的数字字符先转为一个完整的数字,再进行操作(这时候就需要借助上面提到的使用空格分隔数字的技巧了)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static Double toValue(StringBuilder postfix) {
int postLen=postfix.length();
Double result=0.0;
Stack<Double> numStack=new SeqStack<>();
for(int i=0;i<postLen;i++){
char curChar=postfix.charAt(i);
if(curChar>='0'&&curChar<='9'){
result=0.0;
while (curChar!=' '){
result=result*10+curChar-'0';
curChar=postfix.charAt(++i);
}
numStack.push(result);
}
else{
if(curChar!=' '){
double y=numStack.pop();
double x=numStack.pop();
switch (curChar){
case '+':
result=x+y;
break;
case '-':
result=x-y;
break;
case '*':
result=x*y;
break;
case '/':
result=x/y;
break;
case '^':
result=Math.pow(x,y);
break;
}
numStack.push(result);
}
}
}
return result;
}

这样的操作其实不算完美,实际的表达式还可以是浮点数,或者包含更多的括号以及运算符。

就需要进一步的完善了。

smartpig wechat
扫一扫关注微信公众号
0%