数据结构-02 图解中缀表达式转后缀表达式并计算值

目录:

数据结构-01-图解后缀表达式值计算方式数据结构-02 图解中缀表达式转后缀表达式并计算值

1.图解中缀表达式转后缀表达式

通过 数据结构-01-图解后缀表达式值计算方式 我们了解到后缀表达式（例如：9 3 1 - 3 * + 10 2 /+）对计算机运算的方便，但是它却让我们这些人类十分的难受，因此我们需要在设计一个，中缀表达式转后缀表达式的程序来一劳永逸.

规则：依次遍历表达式， 1.如果是数字就添加到后缀表达式上（相反于数据结构-01-图解后缀表达式值计算方式 ） 2.如果是符号就更栈顶Top符号比较优先级，低的输入会导致出栈（就是栈中高于或者等于都会全部出栈到后缀表达式上） （符号的优先顺序为，乘除 > 加减 > 括号（括号的情况比较特殊，请结合代码和图解详细分析））

这里是一个 中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式 "9 3 1 - 3 * + 10 2 /+"的例子（我们使用空格将元素分开)

new 一个空栈 1.第一个是数字9，1.数字就添加到后缀表达式上 2.第二个是+，判断栈顶的，只有低的输入才会导致出栈，因此这里将+加号入栈 3.第三个是左括号 （ ，这里比较特殊，因为是左括号直接入栈 4.第四个是数字3，.数字就添加到后缀表达式上 5.第五个是减号， 我们需要判断栈顶的符号，左括号的优先级是最小的，这里直接将减号入栈 6.第六个是1，.数字就添加到后缀表达式上 7.第七-个是右括号，括号是优先级最低的，特殊，我们直接找到左括号，将括号中的东西减号(-)出栈 8.第八个是乘法，判断符号优先级高于加法，因为只有低级输入才会导致出栈，这里直接入栈 9.第九个是 3，数字直接输出到后缀表达式中 10.第十个是 +，低级输入会导致出栈（这里的+号的等级小于 * 等于 + ，所以栈中的 * 和 +好都会出栈，然后第十个加号入栈） 11.第十一个是 10，数字直接全部输出到后缀表达式（大家请这里思考一个问题:像10这样的2位数或者多位数我们如何遍历得到的是一个元素 10，而不是2个元素 1,0 呢？（后面的代码将会实现这个功能））

12.第十二个是除 / ，符号比较优先级 ，除法的优先级高于加法，只有低输入才会导致出栈，-所以这里直接入栈 13.第十三 是 2，数字直接输出到后缀表达式中，循环结束 14.循环结束后将栈中所有的元素依次出栈，-添加到后缀表达式后面。程序结束

2.代码

如果你不能很好的理解这个代码，建议画出 1.后缀表达式的计算方法-图解 2.图解中缀表达式转后缀表达式

java

/** * @author 嘉文 */ public class InfixToPostfix { public String infixToPostfix(String infix) { //init stack MyStack myStack = new MyStack(infix.length()); //postfix. StringBuilder postfix = new StringBuilder(); int length = infix.length(); for (int i = 0; i < length; i++) { char tempChar; char charAt = infix.charAt(i); switch (charAt) { //左括号直接入栈，不用过多解释 case '(': myStack.push(charAt); break; //如果遇到 +-，低级会导致一次出栈. case '+': case '-': //出栈 while (!myStack.isEmpty()) { tempChar = myStack.pop(); if (tempChar == '(') { myStack.push(tempChar); break; } postfix.append(" ").append(tempChar); } myStack.push(charAt); break; case '*': case '/': while (!myStack.isEmpty()){ tempChar = myStack.pop(); if (tempChar == '('||tempChar == '+' ||tempChar == '-') { myStack.push(tempChar); break; } postfix.append(" ").append(tempChar); } myStack.push(charAt); break; case ')': while (!myStack.isEmpty()){ tempChar = myStack.pop(); if (tempChar != '('){ postfix.append(" ").append(tempChar); }else { break; } } break; default: postfix.append(" ").append(charAt); //if length enough if (i<length-1){ int j = i + 1; char nextNumber = infix.charAt(j); while ((nextNumber+"").matches("^[0-9]*")&&j<length){ postfix.append(nextNumber); nextNumber = infix.charAt(++j); } i = j-1; } break; } } while (!myStack.isEmpty()) { postfix.append(" ").append(myStack.pop()); } return postfix.toString().trim(); } public int getValueOfInfix(String infix){ String postfix = infixToPostfix(infix); String[] items = postfix.split(" "); MyStack myStack = new MyStack(items.length); int length = items.length; for (int i = 0; i < length; i++) { String tempItem = items[i]; switch (tempItem){ case "+": char first = myStack.pop(); char second = myStack.pop(); int result = (int)second + (int)first; myStack.push((char)result); break; case "-": char first2 = myStack.pop(); char second2 = myStack.pop(); int result2 = (int)second2 - (int)first2; myStack.push((char)result2); break; case "*": char first3 = myStack.pop(); char second3 = myStack.pop(); int result3 = (int)second3 * (int)first3; myStack.push((char)result3); break; case "/": char first4 = myStack.pop(); char second4 = myStack.pop(); int result4 = (int)second4 / (int)first4; myStack.push((char)result4); break; //if is number. default: int charInt = Integer.parseInt(tempItem); myStack.push((char)charInt); break; } } return myStack.pop(); } /** * 这是一个简单的栈实现 */ class MyStack { private char[] stackArray; private int topIndex ; public MyStack(int maxSize) { stackArray = new char[maxSize]; topIndex = -1; } public void push(char newTopItem){ stackArray[++topIndex] = newTopItem; } public char pop(){ return stackArray[topIndex--]; } public char peek(){ return stackArray[topIndex]; } public boolean isEmpty(){ return topIndex<0; } } }

测试

public static void main(String[] args) { int valueOfInfix = new InfixToPostfix().getValueOfInfix("9+(3-1)*3+10/2"); System.out.println(valueOfInfix); }

输出： 计算正确