首页 > 代码库 > Dijkstra的双栈算术表达式求值算法 C++实现

Dijkstra的双栈算术表达式求值算法 C++实现

技术分享
 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 template<typename T>
 6 class Stack
 7 {
 8 private:
 9     T stack[100];
10     int i = 0;
11 public:
12     Stack() = default;
13 
14     T pop()
15     {
16         if (i == -1)
17         {
18             cout << "栈已空!" << endl;
19             return 0;
20         }
21 
22         T top = stack[i - 1];
23         --i;
24         return top;
25     }
26 
27     void push(T num)
28     {
29         ++i;
30         stack[i - 1] = num;
31     }
32 
33     void clear()
34     {
35         for (int j = 0; j < 100; ++j)
36         {
37             T[j] = 0;
38         }
39     }
40 };
41 
42 int main()
43 {
44     Stack<string> ops;
45     Stack<double> num;
46     string str;
47 
48     std::cout << "请输入计算式: " << endl;
49     cout << "注: 每个字符间请以空格分开,子表达式请用括号括起注明" << endl;
50     cout << "字符 E 代表结束" << endl;
51     while (true)
52     {
53         cin >> str;
54              if (str == "(")      continue;
55         else if (str == "+") ops.push(str);
56         else if (str == "-") ops.push(str);
57         else if (str == "*") ops.push(str);
58         else if (str == "/") ops.push(str);
59         else if (str == ")")
60         {
61             string op = ops.pop();
62             double val = num.pop();
63             if (op == "+") val = num.pop() + val;
64             if (op == "-") val = num.pop() - val;
65             if (op == "*") val = num.pop() * val;
66             if (op == "/") val = num.pop() / val;
67             num.push(val);
68         }
69 
70         else if (str != "E")
71         {
72             double val = stod(str);
73             num.push(val);
74         }
75              
76         if (str == "E")
77         {
78             break;
79         }
80     }
81 
82     cout << "结果为: ";
83     cout << num.pop() << endl;
84 
85     return 0;
86 }
View Code

技术分享

 

Dijkstra的双栈算术表达式求值算法 C++实现