首页 计算机学科 java 编程题

# 中缀转后缀表达式

| |
| |
| |
| |
---

a + b
a + b - c
a * b + c
a + b * c

# 分析 a + b

|  |
|  |
|  |
|  |
----

a + b                  ab+

首先 遍历到 a 是一个 数字 就加入字符串，再遍历到 + 是个运算符 就加入到 队列中

image-20240116104723897

然后再遍历 到 b 是个数字就加入字符串中，然后从队列中取出运算符并进拼接字符串

image-20240116104840034

# 分析 a + b - c

| |
| |
| |
| |
---

a + b - c

遍历到 a 是个数字 加入到字符串中 ，再遍历到 + 是个 运算符加入到 队列中，再遍历到 b 是个数字加入到字符串中，再遍历到 - 是个运算符加入到队列中，再遍历到 c 是个数字加入到 字符串中

image-20240116105115674

列中然后从队列中取出 - 运算符 拼接后 再 取出 + 拼接到字符串 得到最终结果

image-20240116105222478

# 分析 a * b + c

| |
| |
| |
| |
---

a * b + c

遍历到 a 是数字加入到 字符串，再遍历到 * 是运算符加入到 队列中，再遍历到 b 是数字加入到字符串，再遍历到 + 时 此时 运算符 比 上次的运算符 优先级小

image-20240116105634065

所以需要将上次的 运算符 (*) 拼接到字符串后再 入栈 + 运算符

image-20240116105721348

然后再遍历到 c 是个数字加入到字符串，最后取出 运算符 进行拼接字符串，得到最终结果

image-20240116105817954

# 分析 a + b * c

| |
| |
| |
| |
---

a + b * c

遍历到 a 是个数字加入到字符串，再遍历到 + 是个运算符 加入到 队列，再遍历到 b 是个数字加入到 字符串

image-20240116110045788

再遍历到 * 是个运算符 ，但是这个运算符的优先级高于上次的运算符，需要先运算 * 那么就不能将 + 运算符 出栈，所以让 * 先入栈，继续往后遍历到 c 是个数字 加入到 字符串

image-20240116110256239

然后弹出栈中运算符拼接到字符串得到最终结果

image-20240116110325975

# 总结：

  1. 遇到非运算符 直接拼串
  2. 遇到 + - * /
    1. 它的优先级比栈顶运算符高，入栈
    2. 否则把栈里优先级 >= 它的 都出栈，它再入栈
  3. 遍历完成，栈里剩余运算符依次出栈

# 代码：

/**
     * 返回运算符的 优先级 设定 + - 运算符的优先级为 1 而 * / 运算符的优先级为 2
     * @param ch
     * @return
     */
public int priority(char ch)
{
   // 判断传入的字符
   return switch (ch)
   {
         // 判断 字符 是否为 + 或 - 如果是就返回 1
      case '+', '-' -> 1;
         // 判断 字符 是否为 * 或 / 如果是就返回 2
      case '*', '/' -> 2;
      default -> throw new RuntimeException("非法字符");
   };
}
public String infixToSuffix(String exp)
{
   // 记录 运算符
   LinkedList<Character> stack = new LinkedList<>();
   // 记录 数字
   StringBuilder sb = new StringBuilder();
   for (int i = 0; i < exp.length(); i++)
   {
      // 遍历 每个 字符
      char c = exp.charAt(i);
      switch (c)
      {
            // 判断如果是 运算符 就执行
         case '+', '-', '*', '/' ->
         {
            // 判断 栈中 是否为空
            if (stack.isEmpty())
            {
               // 如果是空 就将 运算符 加入栈中
               stack.push(c);
            }
            else
            {
               // 判断 当前 运算符 的优先级 是否 大于 栈顶的运算符 优先级
               if (priority(c) > priority(stack.peek()))
               {
                  // 如果 当前 运算符 优先级 大于 栈顶的运算符 优先级 那么就 将 当前
                  // 运算符 加入栈中
                  stack.push(c);
               }
               // 相反执行操作
               else
               {
                  // 如果 栈顶运算符的优先级 大于等于 当前运算符 优先级 那么就需要将 栈中的 高优先级
                  // 的运算符 弹出 并 先 进行计算后 进行后续的操作
                  while(! stack.isEmpty() && priority(stack.peek()) >= priority(c))
                  {
                     // 从 栈中取出 栈顶的 运算符 追加到 字符串中
                     sb.append(stack.pop());
                  }
                  stack.push(c);
               }
            }
         }
            // 如果 不是 运算符那么肯定就是 数字 那么就 加入到 字符串中
         default -> sb.append(c);
      }
   }
   // 判断 栈中 如果 不为 空 就 将剩余的 运算符 追加到 字符串中
   while(! stack.isEmpty())
   {
      sb.append(stack.pop());
   }
   // 将最终结果 转换为 字符串 并 返回
   return sb.toString();
}
public static void main(String[] args)
{
   System.out.println(new Demo08().infixToSuffix("a+b"));
   System.out.println(new Demo08().infixToSuffix("a+b-c"));
   System.out.println(new Demo08().infixToSuffix("a+b*c"));
   System.out.println(new Demo08().infixToSuffix("a*b-c"));
}
打印结果：
ab+
ab+c-
abc*+
ab*c-

# 分析 带括号的情况 (a + b) * c
| |
| |
| |
| |
---

(a + b) * c

遍历到 ( 我们可以将 ( 看作为一个运算符 让它先入栈，再遍历到 a 是个数字 加入字符串，再遍历到 + 由于没有 找到 ( 的另一半所以 就 先将 + 直接入栈，再遍历到 b 是个数字加入到 字符串
注意：如果 + 入栈了 说明 它的优先级 应该比 （ 高
image-20240116114224245
再遍历到 ）时 这时 就需要将 直到（ 的运算符都出栈，拼接到字符串中 (除了 () 不需要 拼接到字符串中)
image-20240116114655047
遍历到 * 时 栈中时空的 直接入栈 然后 再遍历到 c 是数字就 拼接到字符串中
image-20240116133736288
最后将 * 弹出 拼接到字符串中
image-20240116133747364
# 分析 带括号的情况 (a - b * c - d) * e
| |
| |
| |
| |
---

(a - b * c - d) * e

遍历到 ( 入栈，再遍历到 a 是数字 拼接到 字符串，再遍历到 - 是运算符 入栈，再遍历到 b 是数字拼接到字符串中，再遍历 * 是运算符 优先级比 栈顶 运算符 优先级高 直接 入栈，再遍历到 c 是数字拼接到 字符串
image-20240116134305862
再遍历到 - 是运算符 它的优先级 比 栈顶的运算符 优先级 低 将 * 运算符 弹出 拼接到字符串中，左括号不用出栈，因为左括号的优先级比 - 号 低 。只有 大于等于 * 优先级的 弹出栈，然后 将 - 入栈，再遍历 d 是数字 拼接到字符串
image-20240116134926498
再遍历是）需要把之前栈中所有的运算符 直到 （左括号 的 都弹出，此时 - 运算符 出栈 并 拼接到 字符串中，同时左括号 也没用了也出栈
image-20240116135059781
再遍历到 * 此时 栈空 直接入栈，再遍历到 e 是数字 拼接到字符串，最后弹出 * 运算符 拼接到字符串
image-20240116135206965
# 总结：
带（）
  • 左括号直接入栈，左括号优先级设置为 0
  • 右括号，遇到右括号就把栈里到左括号为止的所有运算符都出栈 (包括左括号) 即可！
# 代码：
/**
     * 返回运算符的 优先级 设定 + - 运算符的优先级为 1 而 * / 运算符的优先级为 2
     * @param ch
     * @return
     */
public int priority(char ch)
{
   // 判断传入的字符
   return switch (ch)
   {
         // 判断 字符 是否为 + 或 - 如果是就返回 1
      case '+', '-' -> 1;
         // 判断 字符 是否为 * 或 / 如果是就返回 2
      case '*', '/' -> 2;
      case '(' -> 0;
      default -> throw new RuntimeException("非法字符");
   };
}
public String infixToSuffix(String exp)
{
   // 记录 运算符
   LinkedList<Character> stack = new LinkedList<>();
   // 记录 数字
   StringBuilder sb = new StringBuilder();
   for (int i = 0; i < exp.length(); i++)
   {
      // 遍历 每个 字符
      char c = exp.charAt(i);
      switch (c)
      {
            // 判断如果是 运算符 就执行
         case '+', '-', '*', '/' ->
         {
            // 判断 栈中 是否为空
            if (stack.isEmpty())
            {
               // 如果是空 就将 运算符 加入栈中
               stack.push(c);
            }
            else
            {
               // 判断 当前 运算符 的优先级 是否 大于 栈顶的运算符 优先级
               if (priority(c) > priority(stack.peek()))
               {
                  // 如果 当前 运算符 优先级 大于 栈顶的运算符 优先级 那么就 将 当前
                  // 运算符 加入栈中
                  stack.push(c);
               }
               // 相反执行操作
               else
               {
                  // 如果 栈顶运算符的优先级 大于等于 当前运算符 优先级 那么就需要将 栈中的 高优先级
                  // 的运算符 弹出 并 先 进行计算后 进行后续的操作
                  while(! stack.isEmpty() && priority(stack.peek()) >= priority(c))
                  {
                     // 从 栈中取出 栈顶的 运算符 追加到 字符串中
                     sb.append(stack.pop());
                  }
                  stack.push(c);
               }
            }
         }
            // 左括号 直接入栈
         case '(' ->
         {
            stack.push(c);
         }
            // 右括号 ，将 直到 左括号 之间的 运算符 都出栈 追加到 字符串中
         case ')' ->
         {
            // 循环直到 找到了 左括号就 停止
            while(! stack.isEmpty() && stack.peek() != '(')
            {
               // 将 之间的 运算符 都加入字符串中
               sb.append(stack.pop());
            }
            // 最后将 左括号 弹出
            stack.pop();
         }
            // 如果 不是 运算符那么肯定就是 数字 那么就 加入到 字符串中
         default -> sb.append(c);
      }
   }
   // 判断 栈中 如果 不为 空 就 将剩余的 运算符 追加到 字符串中
   while(! stack.isEmpty())
   {
      sb.append(stack.pop());
   }
   // 将最终结果 转换为 字符串 并 返回
   return sb.toString();
}
public static void main(String[] args)
{
   System.out.println(new Demo08().infixToSuffix("a+b"));// ab+
   System.out.println(new Demo08().infixToSuffix("a+b-c"));// abc+-
   System.out.println(new Demo08().infixToSuffix("a+b*c")); // ab*c+
   System.out.println(new Demo08().infixToSuffix("a*b-c")); // ab*c-
   System.out.println("--------------------------------------");
   System.out.println(new Demo08().infixToSuffix("(a+b)*c")); // ab+c*
   System.out.println(new Demo08().infixToSuffix("(a-b*c-d)*e")); // abc*-d-e*
}
打印结果：
ab+
ab+c-
abc*+
ab*c-
--------------------------------------
ab+c*
abc*-d-e*