中缀表达式转换后缀表达式

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

一：思路分析

  1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2

  2. 从左至有扫描中缀表达式

  3. 遇到操作数时，将其压入s2

  4. 遇到运算符时，比较其与s1栈顶运算符的优先级：

    1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将次运算符入栈
    2. 否则，若优先级比较栈顶运算符的高，也将运算符压入s1
    3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次将（4-1）与s1中心耳朵栈顶运算符想比较

  5. 遇到括号时：

    1. 如果是左括号“(”，则直接压入s1
    2. 如果是右括号“)”,则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃

  6. 重复2至5，直到表达式的最右边

  7. 将s1中剩余的运算符依次弹出并压入s2

  8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

    1
    中缀表达式1+((2+3)*4)-5==>后缀表达式123+4*+5-

1574172008981

二：代码实现

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
public List<string> parseSuffixExpressionList(List<string> ls)
    {
        //定义两个栈
        Stack<string> s1 = new Stack<string>();//符号栈
   //  Stack<string> s2 = new Stack<string>();//数值栈[只有入栈，没有出栈]
        List<string> s2 = new List<string>();
        string str = "";
        foreach (var item in ls)
        {
            Regex regExp = new Regex("^\\d+$");//匹配的是多位数
          
            if (regExp.IsMatch(item))
            {
                //如果是数字
                //入栈
                s2.Add(item);
            }
            else if(item=="(")
            {
                s1.Push(item);
            }
            else if (item==")")
            {
                while (s1.Peek()!="(")
                {
                    s2.Add(s1.Pop());
                }
                s1.Pop();//!!!将（弹出s1栈
            }
            else
            {
                //当item小于等于栈顶运算符，将s1栈顶的运算符弹出并加入s2中，再次转到4.1与s1中心的栈顶运算符想比较
                while (s1.Count != 0 && Operation.getValue(s1.Peek())>= Operation.getValue(item))
                {
                    s2.Add(s1.Pop());
                }
                //还需要将item压入栈中
                s1.Push(item);
            }
        }
        //将s1中剩余的运算符依次弹出并加入s2
        while (s1.Count()!=0)
        {
            s2.Add(s1.Pop());
        }
        return s2;
    }
    class Operation
    {
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 2;
        private static int DIV = 2;

        public static int getValue(string operation)
        {
            int result = 0;
            switch (operation)
            {
                case "+":
                    result = ADD;
                break;
                case "-":
                    result = SUB;
                    break;
                case "*":
                    result = MUL;
                    break;
                case "/":
                    result = DIV;
                    break;
                default:
                    Console.WriteLine("不存在该运算符！");
                    break;
            }
            return result;
        }
    }

}

//测试方法
void Main()
{
        string str = "1+((3+2)*4)-5";
        List<string> list = poland.toInfixExpressionList(str);
        
        List<string> list2 = poland.parseSuffixExpressionList(list);
        Console.Write("后缀表达式：");
        for (int i = 0; i < list2.Count; i++)
        {
            Console.Write(list2[i]);
        }
        Console.WriteLine("结果："+poland.calculate(list2));
}

1574338060371

三：地址源码

GitHub源码