利用栈实现计算器，实战挺好

鸣涧

利用栈实现计算器，实战挺好

来源： https://www.cnblogs.com/NoneID/p/15777625.html

1. 中缀表达式 和 后缀表达式

中缀表达式: 顾名思义，操作符在操作数的中间，例如: 1 + 1

后缀表达式: 指操作符在操作后后面 ，例如 1 1 + ， 就代表 中缀表达式 的 1 + 1

关于具体的 请参考: https://baike.baidu.com/item/逆波兰式/128437

2. 关于数据结构: 栈

栈就是一个先进先出的队列

C语言函数之间调用，就是使用栈进行的

参考: https://baike.baidu.com/item/栈/12808149?fr=aladdin

3. 中缀表达式 如何利用栈 转换为后缀表达式

利用栈转换规则如下

遍历中缀表达式

• 
  
  
  • 判断为 数字 直接输出
    
    
• 
  
  
  • 判断为 ( 入栈
    
    
• 
  
  
  • 判断为 ) 则，出栈 直至遇到 (
  • 判断为 * 或 /
    
    
• 
  
  
  • 4.1 判断栈顶元素是否是 * 或 / ， 如果是 则出栈
    4.2 若1不符合规则，再将这个字符入栈
    
    
• 
  
  
  • 5.1 判断栈顶元素是否是 * 或 / ，如果是，则全部出栈，然后再入栈
    5.2 若1不符合，再将这个字符入栈
    
    
  • 判断为 + 或 - ，则
    
    
• 
  
  
  • 若表达式计算完毕，将出栈所有数据
    
    

实际例子

通过栈，将式子 3+2(9+8)/3(3/5) 转换为后缀表达式

开始式子: 3+2*(9+8)/3*(3/5)

开始处理: 3
执行规则1，是数字直接输出

输出: 3

栈:

---

开始处理: +
执行规则 5.2 直接入栈

输出: 3

栈: +

---

开始处理: 2
执行规则1，是数字直接输出

输出: 32

栈: +

---

开始处理: *
执行规则4.2，直接入栈

输出: 32

栈: +*

---

开始处理: (
执行规则2，直接入栈

输出: 32

栈: +*(

---

开始处理: 9
执行规则1，直接入栈

输出: 329

栈: +*(

---

开始处理: +
执行规则5.2，直接入栈

输出: 329

栈: +*(+

---

开始处理: 8
执行规则1，直接入栈

输出: 3298

栈: +*(+

---

开始处理: )
执行规则3，出栈直至遇到 (

输出: 3298+

栈: +*

---

开始处理: /
执行规则4.1，将栈顶元素为*或/直接出栈，然后在入栈该操作符

输出: 3298+*

栈: +/

---

开始处理: 3
执行规则1,直接入栈

输出: 3298+*3

栈: +/

---

开始处理: *
执行规则4.1，将栈顶元素为*或/直接出栈，然后在入栈该操作符

输出: 3298+*3/

栈: +*

---

开始处理: (
执行规则2,直接入栈

输出: 3298+*3/

栈: +*(

---

开始处理: 3
执行规则1,直接入栈

输出: 3298+*3/3

栈: +*(

---

开始处理: /
执行规则4.2,入栈

输出: 3298+*3/3

栈: +*(/

---

开始处理: 5
执行规则1,直接入栈

输出: 3298+*3/35

栈: +*(/

---

开始处理: )
执行规则3,出栈 直至遇到(

输出: 3298+*3/35/

栈: +*

---

开始处理: )
执行规则6,全部出栈

输出: 3298+*3/35/*+

栈:

---

得到中缀表达式: 3298+*3/35/*+

完毕

转换代码 C语言实现:

# include <stdio.h>

int main() {
    // 中缀表达式
    char formula[] = "3+2*(9+8)/3*(3/5)";

    // 栈
    char options[sizeof(formula) * sizeof(char)];
    int stackLen = -1;
   
    printf("%s\n",formula);

    int i;
    for (i = 0; formula!='\0'; i++) {
        // 规则1
        if (formula >= '0' && formula <= '9') {
            printf("%c",formula);
        }

        switch (formula) {
            // 规则2
            case '(': {
                stackLen += 1;
                options[stackLen] =formula;
                break;
            }

            // 规则3
            case ')': {
                while (stackLen >= 0 &&  (options[stackLen] != '(')) {
                    printf("%c",options[stackLen]);
                    stackLen -= 1;
                }
                stackLen-=1;
                break;
            }

            // 规则4
            case '*':
            case '/': {
                while (stackLen >= 0 && (options[stackLen] == '*' || options[stackLen] == '/')) {
                    printf("%c",options[stackLen]);
                    stackLen -= 1;
                }
                stackLen += 1;
                options[stackLen] = formula;
                break;
            }

            // 规则5
            case '+':
            case '-': {
                if (stackLen >= 0 &&  (options[stackLen] == '*' || options[stackLen] == '/')) {
                    while (stackLen >= 0) {
                        printf("%c",options[stackLen]);
                        stackLen -= 1;
                    }
                }
                stackLen += 1;
                options[stackLen] = formula;
                break;
            }
        }
    }

    // 规则6
    while (stackLen >= 0) {
        printf("%c",options[stackLen]);
        stackLen--;
    }

    printf("\n");
}

执行结果

# gcc calTest1.c
# ./a.out
3+2*(9+8)/3*(3/5)
3298+*3/35/*+
#
4. 利用栈 后缀表达式计算结果

利用栈计算后缀表达式规则如下

假设后缀表达式是有效的

遍历后缀表达式

• 
  
  
  • 判断为数字，则进行压栈
  • 判断为操作符(+ - * /)
    2.1 出栈2个元素，m 和 n (对于当前栈而言,m: 栈顶元素 n: 栈顶第二个元素)
    2.2 计算 n 操作符 m ,然后将结果 入栈
    
    

实际例子

通过栈，将计算后缀表达式 3298+*3/35/*+ 的值

式子: 3298+*3/35/*+

开始处理: 3

执行规则1: 直接入栈

栈: 3

---

开始处理: 2

执行规则1: 直接入栈

栈: 3 2

---

开始处理: 9

执行规则1: 直接入栈

栈: 3 2 9

---

开始处理: 8

执行规则1: 直接入栈

栈: 3 2 9 8

---

开始处理: +

执行规则2: 取出2个元素, m:8 n:9 , 并且执行结果（n + m）入栈

栈: 3 2 17

---

开始处理: *

执行规则2: 取出2个元素, m:17 n:2 , 并且执行结果(n * m)入栈

栈: 3 34

---

开始处理: 3

执行规则1: 直接入栈

栈: 3 34 3

---

开始处理: /

执行规则2: 取出2个元素, m:3 n:34 , 并且执行结果(n / m)入栈

栈: 3 11.3

---

开始处理: 3

执行规则1: 直接入栈

栈: 3 11.3 3

---

开始处理: 5

执行规则1: 直接入栈

栈: 3 11.3 3 5

---

开始处理: /

执行规则2: 取出2个元素, m:5 n:3 , 并且执行结果(n / m)入栈

栈: 3 11.3 0.6

---

开始处理: *

执行规则2: 取出2个元素, m:0.6 n:11.3 , 并且执行结果(n * m)入栈

栈: 3 6.8

---

开始处理: +

执行规则2: 取出2个元素, m:6.8 n:3 , 并且执行结果(n + m)入栈

栈: 9.8

---

计算结果: 9.8

完成

用C实现该代码

转换代码 C语言实现:

# include <stdio.h>

int main() {
    // 后缀表达式
    char formula[] = "3298+*3/35/*+";

    // 栈
    float options[sizeof(formula) * sizeof(char)];
    int stackLen = -1;
   
    printf("%s\n",formula);

    int i;
    for(i=0;formula!='\0';i++) {
        // 规则1
        if (formula >= '0' && formula <= '9') {
            stackLen++;
            options[stackLen] = (float)(formula-48);
        } else {
            // 规则2
            float m = options[stackLen];
            stackLen--;

            float n = options[stackLen];
            stackLen--;

            switch (formula) {
                case '*': {
                     stackLen++;
                     options[stackLen] = (n * m);
                     break;
                }
                case '/': {
                     stackLen++;
                     options[stackLen] = (n / m);
                     break;
                }
                case '+': {
                     stackLen++;
                     options[stackLen] = (n + m);
                     break;
                }
                case '-': {
                     stackLen++;
                     options[stackLen] = (n - m);
                     break;
                }
            }
        }
    }

    printf("\n结果为: %.2f\n" , options[0]);
}

执行结果

# ./a.out
3298+*3/35/*+

结果为: 9.80
#