很简单, 还有些不太完善, 只支持一位整数.
1 /*******************************************
2 * file: stack_cal.cpp
3 * author: ideawu
4 * date: 2006-11-17
5 *******************************************/
6
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10
11 typedef enum{
12 Token_Error = 0,
13 Token_Int = 'i',
14 Token_Div = '/',
15 Token_Mul = '*',
16 Token_Sub = '-',
17 Token_Add = '+',
18 Token_Mod = '%',
19 Token_Lp = '(',
20 Token_Rp = ')'
21 }TokenType;
22
23 class Token{
24 public:
25 int type;
26 double value;
27
28 Token(){
29 type = Token_Error;
30 value = 0;
31 }
32 };
33
34 class ArrayStack{
35 private:
36 char * name;
37 Token *tokens;
38 int size;
39 int capacity;
40
41 public:
42 ArrayStack(char* n){
43 name = n;
44 size = 0;
45 capacity = 256;
46 tokens = new Token[capacity];
47 }
48
49 ~ArrayStack(){
50 delete[] tokens;
51 }
52
53 int getSize(){
54 return size;
55 }
56
57 bool isEmpty(){
58 return (size == 0);
59 }
60
61 bool isFull(){
62 return (size == capacity);
63 }
64
65 void push(Token token){
66 if(size < capacity){
67 tokens[size ++] = token;
68 }else{
69 }
70 }
71
72 Token* pop(){
73 if(size > 0){
74 size --;
75 return &tokens[size];
76 }else{
77 return NULL;
78 }
79 }
80
81 Token* peek(){
82 if(size > 0){
83 return &tokens[size-1];
84 }else{
85 return NULL;
86 }
87 }
88
89 void toString(){
90 if(size == 0){
91 printf("%s[0]=\n", name);
92 return;
93 }
94 printf("%s[%d]=", name, size);
95 printf("(");
96 printf("{%c,%.4f}", tokens[0].type, tokens[0].value);
97 for(int i=1; i<size; i++){
98 printf(", {%c,%.4f}", tokens[i].type, tokens[i].value);
99 }
100 printf(")\n");
101 }
102 };
103
104 /*
105 * 归约函数, 从操作数栈和操作符栈各弹出一个元素,
106 * 与操作数栈顶的元素(并未弹出)运算后, 结果存在操作栈顶的元素中.
107 */
108 void calculate(ArrayStack &operandStack, ArrayStack &operatorStack){
109 if(operandStack.getSize() < 2){
110 return;
111 }
112 Token *t1 = operandStack.pop();
113 Token *t2 = operandStack.peek();
114 Token *op = operatorStack.pop();
115 switch(op->type){
116 case '*':
117 t2->value *= t1->value;
118 break;
119 case '/':
120 t2->value /= t1->value;
121 break;
122 case '+':
123 t2->value += t1->value;
124 break;
125 case '-':
126 t2->value -= t1->value;
127 break;
128 default:
129 printf("*********Syntax Error!*********\n");
130 exit(1);
131 break;
132 }
133 }
134
135
136 int main(int argc, char *argv[]){
137 char buffer[256];
138 if(argc > 1){
139 strcpy(buffer, argv[1]);
140 }else{
141 printf("Input the statement(1-256 characters):\n");
142 scanf("%s", buffer);
143 }
144
145 ArrayStack operandStack("operandStack ");
146 ArrayStack operatorStack("operatorStack");
147 int streamLen = strlen(buffer);
148 char c;
149 /*
150 * 需要归约的情况:
151 * 1. 当前的token是整数, 且操作符栈顶元素为'*'或'/';
152 * 2. 当前的token是')';
153 * 3. 当前的token是'+'或'-', 且操作符栈顶元素为'+'或'-';
154 */
155 for(int index=0; index<streamLen; index++){
156 c = buffer[index];
157 Token t;
158 if(c >= '0' && c <= '9'){
159 t.type = Token_Int;
160 t.value = c - '0';
161 operandStack.push(t);
162 if(!operatorStack.isEmpty()){
163 if(operatorStack.peek()->type == '*'
164 || operatorStack.peek()->type == '/'){
165 calculate(operandStack, operatorStack);
166 }
167 }
168 }else{
169 t.type = c;
170 Token *temp;
171 switch(c){
172 case ')':
173 if(operatorStack.isEmpty()){
174 printf("*********Syntax Error!*********\n");
175 exit(0);
176 }
177 temp = operatorStack.peek();
178 if(temp->type == '('){
179 // 使(int) ==> int, 即去掉整数两边的括号后再归约.
180 operatorStack.pop();
181 calculate(operandStack, operatorStack);
182 }else{
183 calculate(operandStack, operatorStack);
184 operatorStack.pop();
185 }
186 break;
187 case '-':
188 case '+':
189 if(!operatorStack.isEmpty()){
190 temp = operatorStack.peek();
191 if(temp->type == '+' || temp->type == '-'){
192 calculate(operandStack, operatorStack);
193 }
194 }
195 operatorStack.push(t);
196 break;
197 default:
198 operatorStack.push(t);
199 break;
200 }
201 }
202 }
203 calculate(operandStack, operatorStack);
204
205 printf("=%f", operandStack.pop()->value);
206 printf("\n");
207 return 0;
208 }
209