# java35th-mycode

**Repository Path**: varcha/java35th-mycode

## Basic Information

- **Project Name**: java35th-mycode
- **Description**: wangdao java35th, from session2, including all my class exercise and homework.
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-09-24
- **Last Updated**: 2021-10-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# java35th-mycode

#### 介绍
wangdao java35th, from session2, including all my class exercise and homework.

## 9.24
1. 学习链表实现栈，队列，作业用数组实现线性表

## 9.25

##### 表达式转换与计算
2. 中缀表达式转换为后缀表达式（逆波兰式，reversed Poland expression 或者 postfix expression）

   - 维护一个操作符**operator**栈

   - 正序遍历中缀表达式，操作数直接输出，操作符：

     - 当前左括号，直接入栈；当前右括号，则栈内元素出栈，直至遇到右括号
     - 栈顶为左括号，入栈
     - 优先级大于栈顶，入栈
     - 优先级小于，或等于栈顶，则栈顶出栈，直至大于栈顶或者栈为空，则入栈。
     - 当表达式遍历完成后，栈内元素全部出栈
   
   - 括号匹配错误判断：
   
     - 右括号一定要最后能通左括号匹配，如果栈为空还无法匹配，一定右括号多了；
     - 如果表达式遍历完成，栈内还存在左括号，则一定左括号多了
   
   - 比较算法：
   
     ```java
      /**
      * opN > opS, return 1, push opN in;
      * opN <= opS, return -1, pop out opS and continue compare;
      * opS cannot be )
      * opS = (, return 1, push opN in;
      * opN = (, return 1, push opN in;
      * opN = ), opS = (, return 0;
      * opN = ), return -1, pop out opS and continue compare;
      */
     private static int compare(char opS, char opN) {
         if (opS == '(') {
             if (opN == ')') return 0;
             return 1;
         }
         if (opN == '(') return 1;
         if (opN == ')') return -1;
         // compare comparator other than parenthesis
         if (opN == opS) return -1;
         if (opN == '^') return 1;
         if (opN == '*' && opS != '^') return 1;
         if (opN == '/' && opS != '^') return 1;
         return -1;
     }
     ```
     
   - 转换算法：
   
     ```java
     public static String postFixTran(String expr) {
         // store postfix expression
         StringBuffer postfix = new StringBuffer();
         // create a stack to store operator and operand
         Stack<Character> operators = new Stack<>();
         for (int i = 0; i < expr.length(); i++) {
             char oper = expr.charAt(i);
             if (isNumber(oper)) {
                 postfix.append(oper);
                 continue;
             }
             boolean stackManuFlag = false;
             while (!operators.isEmpty()) {
                 int flag = compare(operators.peek(), oper);
                 if (flag < 0) {
                     postfix.append(operators.pop());
                 } else if (flag > 0) {
                     break;
                 } else {
                     operators.pop();
                     stackManuFlag = true;
                     break;
                 }
             }
             if (stackManuFlag)
                 continue;
             if (oper == ')')
                 throw new RuntimeException("error expression!");
             operators.push(oper);
         }
         while (!operators.isEmpty()) {
             char oper = operators.pop();
             if (oper == '(' || oper == ')')
                 throw new RuntimeException("error expression!");
             postfix.append(oper);
         }
         return postfix.toString();
     }
     ```
   
3. 后缀表达式计算

   - 维护一个操作数**operand**栈

   - 从左到右遍历后缀表达式，将操作数入栈，遇到操作符时候：

     - 栈顶两个元素出栈，后出栈元素在前，先出栈元素在后，进行相应操作符的运算。
     - 将运算的结果入栈

   - 表达式遍历完成后，栈内只剩一个操作数，即为计算结果；如果出栈后不为空，则一定后缀表达式转换错误

   - 计算算法：

     ```java
     public static double calPostFix(String postfix, int[] numValue) {
         Stack<Double> operands = new Stack<>();
         int count = 0;
         for (int i = 0; i < postfix.length(); i++) {
             char oper = postfix.charAt(i);
             if (isNumber(oper)) {
                 operands.push(((double) numValue[count++]));
             } else {
                 double o2 = operands.pop();
                 double o1 = operands.pop();
                 double r = 0;
                 switch (oper) {
                     case '^':
                         r = Math.pow(o1, o2);
                         break;
                     case '*':
                         r = o1 * o2;
                         break;
                     case '/':
                         r = o1 / o2;
                         break;
                     case '+':
                         r = o1 + o2;
                         break;
                     case '-':
                         r = o1 - o2;
                         break;
                 }
                 operands.push(r);
             }
         }
         double result = operands.pop();
         if (!operands.isEmpty()) throw new RuntimeException("postfix transfer error!");
         return result;
     }
     ```

4. 计算结果示例：

   - 初始化赋值
   ```java
   private static String[] createInfix() {
       Expression expression = new Expression(10);
       expression.add("(a+b)*(c-d)");
       expression.add("a*(b-(c+d))+e/f");
       expression.add("a*b+((c+d)*e/f^g-(h-i)*j)");
       expression.add("a-b*(c+d)/(((e-f)*(g+h))+i)*j");
       expression.add("a-((((a+b)/(c-d)-5)");  // 抛出异常，左括号多不匹配
       expression.add("(a-b)*(c+d))))+e");     // 抛出异常，右括号多
       return expression.settle();
   }
   ```
   
   ![image-20210925153647120](note_ds_image/image-20210925153647120.png)