1 //
2 // Stack.h
3 // 顺序栈
4 //
5 // Created by geshenglu on 2020/3/21.
6 // Copyright © 2020 geshenglu. All rights reserved.
7 //
8
9 #ifndef Stack_h
10 #define Stack_h
11 template<class Elemtype>
12 class Stack
13 {
14 public:
15 virtual bool IsEmpty() const =0;
16 virtual void Push(const Elemtype&x)=0;
17 virtual Elemtype Pop()=0;
18 virtual Elemtype Top()const =0;
19 virtual ~Stack(){};
20 };
21 #endif /* Stack_h */
1 //
2 // SeqStack.h
3 // 顺序栈
4 //
5 // Created by geshenglu on 2020/3/21.
6 // Copyright © 2020 geshenglu. All rights reserved.
7 //
8
9 #ifndef SeqStack_h
10 #define SeqStack_h
11 #include "Stack.h"
12 template<class Elemtype>
13 class SeqStack:public Stack<Elemtype>
14 {
15 private:
16 Elemtype *data;
17 int maxSize;
18 int top_p;
19 void doubleSpace();
20 public:
21 SeqStack(int initSize = 10)
22 {
23 maxSize = initSize;
24 data = new Elemtype[maxSize];
25 top_p = -1;
26 }
27 ~SeqStack()
28 {
29 delete [] data;
30 }
31 virtual bool IsEmpty() const override;
32 virtual void Push(const Elemtype&x)override;
33 virtual Elemtype Pop()override;
34 virtual Elemtype Top()const override;
35 };
36
37 template<class Elemtype>
38 void SeqStack<Elemtype>::doubleSpace()
39 {
40 Elemtype *tmp = data;
41 data = new Elemtype[maxSize*2];
42 for (int i=0; i<maxSize; ++i)
43 data[i] = tmp[i];
44 maxSize *= 2;
45 delete tmp;
46 }
47
48 template<class Elemtype>
49 bool SeqStack<Elemtype>::IsEmpty() const
50 {
51 return top_p == -1;
52 }
53
54 template<class Elemtype>
55 void SeqStack<Elemtype>::Push(const Elemtype&x)
56 {
57 if(top_p == maxSize - 1)
58 {
59 doubleSpace();
60 }
61 data[++top_p]=x;
62 }
63
64 template<class Elemtype>
65 Elemtype SeqStack<Elemtype>::Pop()
66 {
67 return data[top_p--];
68 }
69
70
71 template<class Elemtype>
72 Elemtype SeqStack<Elemtype>::Top() const
73 {
74 return data[top_p];
75 }
76
77 #endif /* SeqStack_h */
1 //
2 // Created by geshenglu on 2020/4/4.
3 //
4
5 #ifndef CALC_H
6 #define CALC_H
7 #include "SeqStack.h"
8 #include <string>
9 class Calc {
10 char *expression;
11 enum class token{
12 OPAREN,ADD,SUB,MULTI,DIV,EXP,CPAREN,VALUE,EOL
13 };
14 void BinaryOp(token op,SeqStack<int>&dataStack);
15 token GetOp(int &value);
16 public:
17 Calc(char *s){
18 expression = new char[strlen(s)+1];
19 strcpy(expression,s);
20 }
21 ~Calc(){
22 delete expression;
23 }
24 int result();
25 };
26 #endif //CALC_H
1 //
2 // Created by geshenglu on 2020/4/4.
3 //
4
5 #include "Calc.h"
6 #include <iostream>
7 #include <cmath>
8 void Calc::BinaryOp(Calc::token op, SeqStack<int> &dataStack) {
9 int num1,num2;
10 if(dataStack.IsEmpty()){
11 std::cerr<<"缺少右操作数！"<<std::endl;
12 exit(1);
13 }
14 else
15 num2 = dataStack.Pop();
16
17 if(dataStack.IsEmpty()){
18 std::cerr<<"缺少左操作数！"<<std::endl;
19 exit(1);
20 }
21 else
22 num1 = dataStack.Pop();
23
24 switch(op){
25 case token::ADD:
26 dataStack.Push(num1+num2);
27 break;
28 case token::SUB:
29 dataStack.Push(num1-num2);
30 break;
31 case token::MULTI:
32 dataStack.Push(num1*num2);
33 break;
34 case token::DIV:
35 dataStack.Push(num1/num2);
36 break;
37 case token::EXP:
38 dataStack.Push(pow(num1,num2));
39 break;
40 }
41 }
42
43 Calc::token Calc::GetOp(int &value) {
44 while (*expression && *expression == ' '){
45 ++expression;
46 }
47 if(*expression=='\0'){
48 return token::EOL;
49 }
50 if(*expression>='0' && *expression<='9'){
51 value = 0;
52 while (*expression>='0' && *expression<='9'){
53 value = value*10 + *expression - '0';
54 ++expression;
55 }
56 return token::VALUE;
57 }
58 switch(*expression){
59 case '(':
60 ++expression;
61 return token::OPAREN;
62 case ')':
63 ++expression;
64 return token::CPAREN;
65 case '+':
66 ++expression;
67 return token::ADD;
68 case '-':
69 ++expression;
70 return token::SUB;
71 case '*':
72 ++expression;
73 return token::MULTI;
74 case '/':
75 ++expression;
76 return token::DIV;
77 case '^':
78 ++expression;
79 return token::EXP;
80 }
81 }
82
83 int Calc::result() {
84 token lastOp,topOp;
85 int result_value,CurrentValue;
86 SeqStack<token> opStack;
87 SeqStack<int> dataStack;
88 char *str = expression;
89 while((lastOp = GetOp(CurrentValue))!=token::EOL){
90 switch(lastOp){
91 case token::VALUE:
92 dataStack.Push(CurrentValue);
93 break;
94 case token::CPAREN:
95 while (!opStack.IsEmpty() && (topOp = opStack.Pop())!=token::OPAREN){
96 BinaryOp(topOp,dataStack);
97 }
98 if(topOp!=token::OPAREN){
99 std::cerr<<"缺失左括号"<<std::endl;
100 }
101 break;
102 case token::OPAREN:
103 opStack.Push(token::OPAREN);
104 break;
105 case token::EXP:
106 opStack.Push(token::EXP);
107 break;
108 case token::MULTI:
109 case token::DIV:
110 while (!opStack.IsEmpty() && (opStack.Top())>=token::MULTI){
111 BinaryOp(opStack.Pop(),dataStack);
112 }
113 opStack.Push(lastOp);
114 break;
115 case token::ADD:
116 case token::SUB:
117 while (!opStack.IsEmpty() && (opStack.Top())!=token::OPAREN){
118 BinaryOp(opStack.Pop(),dataStack);
119 }
120 opStack.Push(lastOp);
121 break;
122 }
123 }
124
125 while (!opStack.IsEmpty()){
126 BinaryOp(opStack.Pop(),dataStack);
127 }
128
129 if(dataStack.IsEmpty()){
130 std::cout<<"无结果!"<<std::endl;
131 return 0;
132 }
133 result_value = dataStack.Pop();
134 if(!dataStack.IsEmpty()){
135 std::cout<<"缺操作符!"<<std::endl;
136 return 0;
137 }
138 expression = str;
139 return result_value;
140 }
1 #include <iostream>
2 #include "Calc.h"
3 int main() {
4 Calc exp1("3*(1+1)^2^3/(4-2)-10*99+ 1 -13");
5 std::cout<<exp1.result()<<std::endl;
6 return 0;
7 }