文章目录
中缀表达式
中缀表达式（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是中缀形式处于操作数的中间（例：3 + 4，3 + 5 * 4 - 2），中缀表达式是人们常用的算术表示方法。
如何编写一个程序，直接指向计算中缀表达式呢？下面我提供两种方法。
中缀表达式的计算
利用双栈来实现中缀表达式的计算
中缀表达式以字符串的显示给出，例：“30 - 2 * 22 - 31 * 1 + 100 - 20 - 1”;
思路如下：
- 创建两个栈，
数字栈(numStack)，和字符栈(operStack)。 - 通过一个下标
index来遍历中缀表达式。 - 遇到数字，直接入数字栈。
- 遇到字符，分为三种情况：
（1）若符号栈为空，直接入符号栈。
（2）若该字符运算优先级大于字符栈栈顶元素，直接入符号栈。
（3）若该字符运算优先级小于或者等于字符栈栈顶元素，那么需要从数字栈栈顶弹出两个数字，符号栈栈顶弹出一个字符，进行运算，然后将运算结果加入数字栈。此时，需要继续比较index指向的字符与栈顶字符优先级，重复(2)(3)操作，直到该字符运算优先级大于字符栈栈顶元素，直接入符号栈。 - 当表达式遍历完之后，就顺序从字符栈和数栈弹出元素进行计算，并将结果存入数字栈，直到数字栈只有一个元素，该元素就是表达式的运算结果。
注意：
- 要注意多为数的情况。
- 表达式中可能会有空格，遇到空格时要直接跳过。
- 这里没有考虑有括号的情况，以及表达式开头是负数的情况，后面会考虑。
代码实现：
public class Infix { //判断是否是运算符 public static boolean isOper(char ch){ return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } //判断运算符优先级 public static int priority(char oper){ if(oper == '*' || oper == '/') return 1; else if(oper == '+' || oper == '-') return 0; else return -1; } //进行运算 public static int operation(int num1 , int num2, char oper){ switch (oper){ case '+': return num1 + num2; case '-': return num2 - num1; case '*': return num2 * num1; case '/': return num2 / num1; default: return -1; } } public static int evaluate(String s){ //用来保存遍历到的字符 char ch = ' '; //后面用来保存运算结果 int rst = 0; //遍历字符串的下标 int index = -1; //遇到多位数时，用来拼接字符的字符串 String keepNum = ""; Deque<Integer> numStack = new LinkedList<>(); Deque<Character> operStack = new LinkedList<>(); while(true){ index++; //字符串遍历结束，循环终止 if(index >= s.length()) break; //获得下标处的字符串 ch = s.charAt(index); //遇到空格直接跳过 if(ch == ' ') continue; //ch是数字，直接入栈 if(!isOper(ch)){ int i = index; while(i != s.length() && !isOper(s.charAt(i)) && s.charAt(i) != ' '){ keepNum += s.charAt(i); i++; } index = i - 1; numStack.push(Integer.parseInt(keepNum)); keepNum = ""; } //ch不是数字 else{ //运算符栈为空,直接入栈 if(operStack.isEmpty()){ operStack.push(ch); } //运算符栈不为空 else{ //若运算符栈栈顶元素优先级大于或等于ch优先级，数栈出两个元素， // 运算符栈出一个元素，进行运算，并将结果入栈,然后将当前运算符入栈 while(!operStack.isEmpty() && priority(operStack.peek()) >= priority(ch)){ rst = operation(numStack.pop() ,numStack.pop() ,operStack.pop()); numStack.push(rst); } //若栈顶运算符优先级小于ch，直接入栈 operStack.push(ch); } } } //当表达式遍历完之后，就顺序从字符栈和数栈弹出元素进行计算， // 并将结果存入数字栈，直到数字栈只有一个元素，该元素就是表达式的运算结果。 while(!operStack.isEmpty()){ rst = operation(numStack.pop(),numStack.pop(),operStack.pop()); numStack.push(rst); } return numStack.pop(); } public static void main(String[] args) { System.out.println(evaluate1("20 -3 *4 /3+2")); } }
利用单栈实现中缀表达式计算
思路如下：
- 创建一个栈，用来存储数字。
- 使用循环来遍历表达式，下标为 i 。
- 定义一个
flag，初始时赋值为0；当遇到' * '时，flag置为1；遇到' / '时，flag置为2；遇到' - '时 ，flag置为3；遇到' + '，flag置为0。 - 遇到数字时：
（1）若flag为0，将该数字直接入栈。
（2）若flag为1，将栈顶数字弹出，与该数子进行乘法运算，结果入栈。
（3）若flag为2，将栈顶数字弹出，做被除数，与该数字进行除法运算，结果入栈。
（4）若flag为3，将该数字变为它的相反数，然后入栈。 - 最后将栈中数字依次弹出，并且相加，结果就是表达式结果。
代码如下：
public class Infix { static int evaluate(String s){ char ch = ' '; int rst = 0; int index = -1; //在判断多位数时，用于字符串的拼接 String str = ""; int flag = 0; Stack<Integer> st = new Stack<>(); for(int i = 0; i < s.length(); i++){ ch = s.charAt(i); if(ch == ' ') continue; //ch是数字 if(ch >= '0' && ch <= '9'){ //判断多位数情况 str = ch + ""; int j = i + 1; while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <='9'){ str += s.charAt(j); j++; } i = j - 1; rst = Integer.parseInt(str); if(flag == 1){ rst *= st.pop(); } else if(flag == 2){ rst =st.pop() / rst; } else if(flag == 3){ rst *= -1; } st.push(rst); flag = 0; } //ch是运算符 else{ if(ch == '*') flag = 1; else if(ch == '/') flag = 2; else if(ch == '-') flag = 3; else flag = 0; } } //将栈里面的数字求和 while(st.size() != 1){ st.push(st.pop() + st.pop()); } return st.pop(); } public static void main(String[] args) { System.out.println(evaluate("20 -3 *4 /3+2")); } }
后缀表达式
后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。
例：(3 + 4)* 5 - 6 ===> 3 4 + 5 * 6 -
后缀表达式的计算
思路如下：
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算(次项元素和栈顶元素)，并将结果入栈;重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如: (3+4)X5-6对应的前缀表达式就是34+5 X 6-,针对后缀表达式求值步骤如下:
- 从左至右扫描，将3和4压入堆栈;
- 遇到+运算符，因此弹出4和3 (4为栈项元素，3为次顶元素)，计算出3+4的、值，得7，再将7入栈;
- 将5入栈;
- 接下来是X运算符，因此弹出5和7，计算出7X5=35，将35入栈;
- 将6入栈;
- 最后是 - 运算符，计算出35-6的值，即29， 由此得出最终结果;
代码如下：
注意：后缀表达式以List的形式给出。
//后缀表达式求值 public static int evaluate(List<String> tokens){ Stack<Integer> Stack = new Stack<>(); String s = ""; int rst = 0; for(int i = 0; i < tokens.size(); i++){ s = tokens.get(i); //如果是运算符 if(isOpear(s)){ rst = operation(Stack.pop(),Stack.pop(),s); Stack.push(rst); } else{ Stack.push(Integer.parseInt(s)); } } return Stack.pop(); }
中缀表达式转后缀表达式
思路如下：
与转换为前缀表达式相似，步骤如下：
- 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
- 从左至右扫描中缀表达式；
- 遇到操作数时，将其压s2；
- 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
(1) 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
(2) 否则，若优先级比栈顶运算符的高，也将运算符压入 s1;
(3) 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 4 - (1)与s1中新的栈顶运算符相比较； - 遇到括号时：
(1) 如果是左括号“(”，则直接压入 s1；
(2) 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃； - 重复步骤 2 至 5 ，直到表达式的最右边；
- 将 s1 中剩余的运算符依次弹出并压入 s2；
- 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。
注意：
- 同样要考虑多位数的情况，以及表达式中的空格。
- 要考虑负数开头的情况，如 ：-1 - 2；我们可以判断一下，若表达式中第一个有效字符为负号时，可以往 s2 中直接压入一个0，这样 -1 - 2就转换为了 0 - 1 - 2。
- 考虑括号里面第一个有效字符是负号的情况，如：1 - （ - 1 - 1），同样的，往s2中直接压入一个0，就将式子转换为了1 - （0 - 1 - 1） 。
例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：
代码如下：
static List<String> infixToSuffix(String s){ Stack<String> s1 = new Stack<>(); List<String> s2 = new ArrayList<>(); int i = 0; while(s.charAt(i) == ' '){ i++; } if(s.charAt(i) == '-'){ s2.add("0"); } String str = ""; char ch = ' '; for(; i < s.length(); i++){ ch = s.charAt(i); if(ch == ' ') continue; //如果是数字 if(ch >= '0' && ch <='9'){ //注意多位数的情况 int j = i + 1; //str赋初值 str = ch + "" ; while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9'){ str += s.charAt(j); j++; } s2 .add(str); i = j - 1; } else{ //当ch == ')'时，将s1中的符号不断弹出s2，直到遇到了"(" if(ch == ')'){ while(!s1.isEmpty() && !s1.peek().equals("(")){ s2 .add(s1.pop()) ; } //将"("弹出s1 s1.pop(); } else if(ch == '('){ s1.push(ch+""); if(s.charAt(i+1) == '-'){ s2.add("0"); } } //当ch == '('时直接入s1,当栈顶为'('时，ch直接入s1 else if(s1.isEmpty() || s1.peek().equals("(")) s1.push(ch+""); //当ch优先级大于栈顶符号优先级时，ch直接入栈 else if(priority(ch) > priority(s1.peek().charAt(0))){ s1.push(ch + ""); } //将s1栈顶元素加入s2，直到s1栈顶元素优先级小于ch,再将ch入s1 else{ do{ s2 .add(s1.pop()); }while(!s1.isEmpty() && priority(ch) <= priority(s1.peek().charAt(0))); s1.push(ch + ""); } } } //最后将s1中元素全部加入s2 while(!s1.isEmpty()){ s2.add(s1.pop()); } return s2; }
力扣上相应的练习：
