栈解决表达式运算

发表于 | 分类于 | 阅读次数: |
字数统计: 682

一：问题描述

使用栈计算：
$$
722-5+1-5+3-4的值，
$$
模拟计算机的底层操作！

二：思路分析

1574057233983

三：代码实现

使用数组设置的栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
public class ArrayStack2
    {
        private int maxsize;//声明栈的长度
        private int top = -1;//栈顶
        private int[] stack;
        //构造器
        public ArrayStack2(int maxsize)
        {
            this.maxsize = maxsize;
            stack = new int[maxsize];
        }
        //栈满
        public bool isFull()
        {
            return top == maxsize - 1;
        }
        //栈空
        public bool isEmpty()
        {
            return top == -1;
        }
        //入栈-push
        public void push(int n)
        {
            if (isFull())
            {
                Console.WriteLine("栈满，无法添加！");
                return;
            }
            top++;
            stack[top] = n;
        }
        //出栈-pop
        public int pop()
        {
            if (isEmpty())
            {
                throw new Exception("栈空，无法出栈！");
            }
            int value = stack[top];
            top--;
            return value;
        }
        //遍历栈
        public void showlist()
        {
            if (isEmpty())
            {
                throw new Exception("栈空，无法出栈！");
            }
            for (int i = top; i >= 0; i--)
            {
                Console.WriteLine(pop());
            }
        }
        //返回运算符的优先级，优先级是程序员来确定。
        //优先级使用数字表示，数字越大优先级越高。
        public int priority(int oper)
        {
            if (oper=='*'||oper=='/')
            {
                return 1;
            }
            else if (oper == '+' || oper == '-')
            {
                return 0;
            }
            else
            {
                return -1;
            }
        }
        //判断是不是一个运算符
        public bool isOper(char val)
        {
            return val == '+' || val == '-' || val == '*' || val == '/';
        }
        //计算方法
        public int cal(int num1,int num2,int oper)
        {
            int res = 0;
            switch (oper)
            {
                case '+':
                    res= num1 + num2;
                    break;
                case '-':
                    res = num2 - num1;
                    break;
                case '*':
                    res = num1 * num2;
                    break;
                case '/':
                    res = num1 / num2;
                    break;
                default:
                    break;
            }
            return res;
        }
        //可以返回当前栈顶的值
        public int peek()
        {
            return stack[top];
        }
        
    }

在Main函数中执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
static void Main(string[] args)
      {
       #region 计算表达式(只能计算1-9的加、减、乘、除操作！)
          string str = "7+2*6-4*2";
          char[] vs = str.ToCharArray();
          //声明两个栈，一个存放数字，一个存放符合
          ArrayStack2 numstack = new ArrayStack2(10);
          ArrayStack2 operstack = new ArrayStack2(10);
          int index = 0;
          int num1 = 0;
          int num2 = 0;
          int oper = 0;
          int res = 0;
          char ch = ' ';
          while (true)
          {
              //依次得str的每一个字符
              ch = vs[index];
              //判断ch是什么，然后做相应的处理
              if (operstack.isOper(ch))
              {
                  //判断当前的字符栈是否为空
                  if (!operstack.isEmpty())
                  {
                      if (operstack.priority(ch) <= operstack.priority(operstack.peek()))
                      {
                          num1 = numstack.pop();
                          num2 = numstack.pop();
                          oper = operstack.pop();
                          res = numstack.cal(num1, num2, oper);
                          //入栈
                          numstack.push(res);
                          //当前符号入符号栈
                          operstack.push(ch);
                      }
                      else
                      {
                          operstack.push(ch);
                      }
                  }
                  else
                  {
                      //数字入栈
                      operstack.push(ch);
                  }
              }
              else
              {
                  numstack.push(ch - 48);
              }
              index++;
              if (index >= vs.Length)
              {
                  break;
              }
          }

          while (true)
          {
              //如果符号栈为空，则计算到最后的结果，数栈就是最终的结果
              if (operstack.isEmpty())
              {
                  break;
              }
              num1 = numstack.pop();
              num2 = numstack.pop();
              oper = operstack.pop();
              res = numstack.cal(num1, num2, oper);
              //入栈
              numstack.push(res);
          }

          Console.WriteLine("表达式：{0}的结果={1}", str, numstack.pop());
          #endregion

          Console.ReadKey();
      }

四：源码地址

Github源码地址