将中缀表达式转前缀或后缀表达式并计算
2017-12-25 本文已影响0人
不姓马的小马哥
参考了http://blog.csdn.net/zhangkunrun/article/details/41699173的解释,代码部分自己完成了,做个小笔记.
举例：
(3 + 4) * 5 - 6 就是中缀表达式
-*+ 3 4 5 6 前缀表达式
3 4 + 5 * 6 - 后缀表达式
这里说点细节:
1.前缀表达式是从右往左扫描的,后缀表达式是从左往右扫描的.
2.前缀表达式遇到右括号是直接压入运算符栈的,遇到左括号就会把运算符出栈然后压入中间结果栈,直到遇到左括号,然后把两个括号都丢弃.后缀表达式反之.
3.在遇到运算符的时候,会需要判断本运算符和运算符栈栈顶运算符的优先级,在前缀表达式中是本运算符高或者等于栈顶运算符时将本运算符压入运算符栈;而后缀表达式是本运算符高于栈顶运算符时才将本运算符压入运算符栈.
4.在中缀表达式转前缀或后缀表达式的最后,前缀表达式是直接把中间结果栈的元素依次输出就是前缀表达式了,而后缀表达式需要依次输出中间结果栈的元素之后再逆序.
5.在用前缀表达式进行计算的时候,遇到运算符时，弹出栈顶的两个数,用运算符对它们做相应的计算的时候,用栈顶元素 op 次顶元素;;相反后缀表达式的话是用次顶元素 op 栈顶元素
中缀表达式转前缀表达式并计算的代码:
/** 把中缀表达式转前缀表达式后再计算
* 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，
* 用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；
* 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
* @param zhongExpression
* @return
*/
public static int calculateQianZhui(String zhongExpression) {
//先把中缀表达式转前缀表达式
String qianExpression = zhong2Qian(zhongExpression);
//从右至左扫描表达式的话要先把字符串逆序
qianExpression = reverseString(qianExpression);
char[] chars = qianExpression.toCharArray();
Stack<Integer> resultValues = new Stack<>();
for (char theChar : chars){
//遇到数字时，将数字压入堆栈,这里要注意字符数字转int,不能直接用integer.valueOf,这样会转成字符的ascii码
if (Character.isDigit(theChar))
resultValues.push(Integer.valueOf(String.valueOf(theChar)));
//遇到运算符时，弹出栈顶的两个数,用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈;
else {
int a = resultValues.pop();
int b = resultValues.pop();
resultValues.push(calculate(a,b,theChar));
}
}
return resultValues.pop();
}
/**
* 中缀表达式转前缀表达式.
* (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
* (2) 从右至左扫描中缀表达式；
* (3) 遇到操作数时，将其压入S2；
* (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
* (4-1) 如果S1为空，则直接将此运算符入栈；
* (4-2) 否则，若优先级比栈顶运算符的较高或相等(后缀表达式中是较高,没有相等)或栈顶运算符为右括号“)”，也将运算符压入S1；
* (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
* (5) 遇到括号时：
* (5-1) 如果是右括号“)”，则直接压入S1；
* (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
* (6) 重复步骤(2)至(5)，直到表达式的最左边；
* (7) 将S1中剩余的运算符依次弹出并压入S2；
* (8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
* (后缀表达式这里要将字符串反转输出,这里直接输出即可)
*
* @param expression
* @return
*/
private static String zhong2Qian(String expression) {
//(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2;
Stack<Character> ops = new Stack<>();
Stack<Character> resultValues = new Stack<>();
//(2) 从右至左扫描中缀表达式;这里是先反转字符串再遍历其字符数组
expression = reverseString(expression);
char[] chars = expression.toCharArray();
for (char theChar : chars) {
//(3) 遇到操作数时，将其压入S2;
if (Character.isDigit(theChar))
resultValues.push(theChar);
//(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
else if (theChar == '+' || theChar == '-' || theChar == '*' || theChar == '/') {
dealTheChar(ops, resultValues, theChar);
}
//(5-1) 如果是右括号“)”，则直接压入S1；
else if (theChar == ')')
ops.push(theChar);
//(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃;
else if (theChar == '(') {
char opsChar = ops.pop();
while (opsChar != (')')) {
resultValues.push(opsChar);
opsChar = ops.pop();
}
}
}
//(7)将S1中剩余的运算符依次弹出并压入S2；
while (!ops.empty()) {
resultValues.push(ops.pop());
}
//(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
// (后缀表达式这里要将字符串反转输出,这里直接输出即可)
StringBuilder exp = new StringBuilder();
while (!resultValues.empty())
exp.append(resultValues.pop());
return exp.toString();
}
private static String reverseString(String expression) {
int n = expression.length();
char[] chars = expression.toCharArray();
for (int i = 0 ; i < n/2 ; i++) {
char temp = chars[i];
chars[i] = chars[n-1-i];
chars[n-1-i] = temp;
}
return String.valueOf(chars);
}
private static void dealTheChar(Stack<Character> ops, Stack<Character> resultValues, char theChar) {
//(4-1) 如果S1为空，则直接将此运算符入栈;
if (ops.empty()) {
ops.push(theChar);
return;
}
char popTheChar = ops.pop().charValue();
//(4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈;
//(4-2) 否则，若优先级比栈顶运算符的较高或相等(后缀表达式中是较高,没有相等)或栈顶运算符为右括号“)”，，也将运算符压入S1；
if (popTheChar == ')' || getPriorityValue(theChar) >= getPriorityValue(popTheChar)) {
ops.push(popTheChar);
ops.push(theChar);
}
//(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较;
else {
resultValues.push(popTheChar);
dealTheChar(ops, resultValues, theChar);
}
}
private static int getPriorityValue(char c) {
if (c == '+' || c == '-')
return 0;
if (c == '*' || c == '/')
return 1;
throw new RuntimeException("非法操作符");
}
private static int calculate(int a,int b,char c) {
switch (c){
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
default:
throw new RuntimeException("非法操作符");
}
}
中缀表达式转后缀表达式并计算的代码:
/**
* 后缀表达式的计算机求值：
* 与前缀表达式类似，只是顺序是从左至右：
* 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，
* 弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），
* 并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
* @param zhongExpression
* @return
*/
public static int calculateQianHou(String zhongExpression) {
//先把中缀表达式转后缀表达式
String HouExpression = zhong2hou(zhongExpression);
char[] chars = HouExpression.toCharArray();
Stack<Integer> resultValues = new Stack<>();
for (char theChar : chars){
//从左至右扫描表达式，遇到数字时，将数字压入堆栈
if (Character.isDigit(theChar))
resultValues.push(Integer.valueOf(String.valueOf(theChar)));
//遇到运算符时,弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素）
// (注意前缀表达式计算是栈顶元素 op 次顶元素)
else {
int a = resultValues.pop();
int b = resultValues.pop();
resultValues.push(calculate(b,a,theChar));
}
}
return resultValues.pop();
}
/**
* 将中缀表达式转换为后缀表达式：
与转换为前缀表达式相似，遵循以下步骤：
* (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
* (2) 从左至右扫描中缀表达式；
* (3) 遇到操作数时，将其压入S2；
* (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
* (4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
* (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
* (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
* (5) 遇到括号时：
* (5-1) 如果是左括号“(”，则直接压入S1；
* (5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
* (6) 重复步骤(2)至(5)，直到表达式的最右边；
* (7) 将S1中剩余的运算符依次弹出并压入S2；
* (8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
* @return
*/
private static String zhong2hou(String expression) {
//(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
Stack<Character> ops = new Stack<>();
Stack<Character> resultValues = new Stack<>();
char[] chars = expression.toCharArray();
//(2) 从左至右扫描中缀表达式；
for (char theChar : chars){
//(3) 遇到操作数时，将其压入S2；
if (Character.isDigit(theChar))
resultValues.push(theChar);
//(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
else if (theChar == '+' || theChar == '-' || theChar == '*' || theChar == '/')
dealTheChar(ops,resultValues,theChar);
//(5) 遇到括号时：
//(5-1) 如果是左括号“(”，则直接压入S1；
else if (theChar == '(')
ops.push(theChar);
//(5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
else if (theChar == ')'){
char opsChar = ops.pop();
while (opsChar != '(') {
resultValues.push(opsChar);
opsChar = ops.pop();
}
}
}
//(7) 将S1中剩余的运算符依次弹出并压入S2；
while (!ops.isEmpty())
resultValues.push(ops.pop());
//(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
StringBuilder exp = new StringBuilder();
while (!resultValues.empty())
exp.append(resultValues.pop());
return reverseString(exp.toString());
}
private static void dealTheChar(Stack<Character> ops, Stack<Character> resultValues, char theChar) {
//(4-1) 如果S1为空，则直接将此运算符入栈;
if (ops.empty()) {
ops.push(theChar);
return;
}
char popTheChar = ops.pop().charValue();
//(4-1) 如果S1为空，或栈顶运算符为右括号“(”，则直接将此运算符入栈;
//(4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）
if (popTheChar == '(' || getPriorityValue(theChar) > getPriorityValue(popTheChar)) {
ops.push(popTheChar);
ops.push(theChar);
}
//(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中
else {
resultValues.push(popTheChar);
//，再次转到(4-1)与S1中新的栈顶运算符相比较;
dealTheChar(ops, resultValues, theChar);
}
}
private static int getPriorityValue(char c) {
if (c == '+' || c == '-')
return 0;
if (c == '*' || c == '/')
return 1;
throw new RuntimeException("非法操作符");
}
private static int calculate(int a,int b,char c) {
switch (c){
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
default:
throw new RuntimeException("非法操作符");
}
}
private static String reverseString(String string) {
int n = string.length();
char[] chars = string.toCharArray();
for (int i = 0; i < n/2; i++) {
char temp = chars[i];
chars[i] = chars[n-1-i];
chars[n-1-i] = temp;
}
return String.valueOf(chars);
}
