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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
// This program will evaluate an arithmetic expression. All of the numbers are assumed
// to be single digit and there will be no blanks between elements of the statements.
// This program assumes that there are no errors in the input. There is minimal error
// reporting.
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
// Computes the precedence of an operator.
int prec( char op );
// Applies an operator to numbers.
long evaluate( char op, long x, long y );
int main( )
{
long nst[41]; // The number stack.
long ntop = -1; // The top of the number stack.
char ost[41]; // The operator stack.
long otop = -1; // The top of the operator stack.
// Prompt the user for an expresion and read it.
string ebuff; // Buffers the arithmetic expression.
int ie = 0; // Indexes the arithmetic expression.
cout << "enter arithmetic expression:\n";
getline(cin, ebuff);
// Let's stick a special character at the end of the string.
ebuff += ']';
// Put the beginning of line character in the operator stack.
otop = 0;
ost[0] = '[';
// Scan throught the expression one character at a time.
bool expectNumber = true; // For primative error detection.
for( ie = 0; ; ie++ ) {
// Buffer the next character.
char nchar = ebuff[ie];
// If the next character is a blank or tab, there is nothing to do.
if( nchar == ' ' || nchar == '\t' ) {
continue;
}
// Stack the numbers immediately.
if( nchar >= '0' && nchar <= '9' ) {
bool checkNext = 0;
double num;
ntop++;
nst[ntop] = nchar - '0';
//Here are my attempts at making it try to recognize a multi digit number.
if (ebuff[ie+1] >= '0' && ebuff[ie+1] <= '9'){
checkNext = 1;
}
if (checkNext == 1){
num = (nchar - '0')*10;
}
if( !expectNumber ) {
cout << "Syntax error" << endl;
exit( 1 );
}
expectNumber = false;
continue;
}
// We must have an operator. If it is a left parentheses, stack it.
if( nchar == '(' ) {
otop++;
ost[otop] = '(';
if( !expectNumber ) {
cout << "Syntax error" << endl;
exit( 1 );
}
expectNumber = true;
continue;
}
// We must have an operator.
if( expectNumber ) {
cout << "Syntax error" << endl;
exit( 1 );
}
// Perform as may operations from the stack as the precedence allows.
while( prec( ost[otop] ) >= prec( nchar ) ) {
// Left paren or [ in stack means we have nothing left to
// evaluate.
if( ost[otop] == '[' || ost[otop] == '(' ) break;
// Perform the indicated operation.
nst[ntop-1] = evaluate( ost[otop], nst[ntop-1], nst[ntop] );
ntop--;
otop--;
}
// If we broke out because of matching the beginning of the line,
// the number on the top of the stack is the result.
if( nchar == ']' ) {
if( ost[otop] == '(' ) {
cout << "Imbalanced parentheses" << endl;
exit( 1 );
}
cout << "value of expression is: " << nst[ntop] << endl;
return 0;
}
// If we broke out due to mataching parens, pop the paren out of the
// stack.
if( ost[otop] == '(' && nchar == ')' ) {
otop--;
expectNumber = false;
continue;
}
if( nchar == ')' ) {
cout << "Imbalanced parentheses" << endl;
exit( 1 );
}
// Stack the operator that we could not evaluate.
otop++;
ost[otop] = nchar;
expectNumber = true;
continue;
}
}
// Function to return the precedence value for an operator.
int prec( char op )
{
switch( op ) {
case '[':
return 0;
case ']':
return 0;
case '(':
return 1;
case ')':
return 1;
case '+':
return 5;
case '-':
return 5;
case '*':
return 10;
case '/':
return 10;
case '^':
return 15;
default:
cout << "Illegal operator\n";
exit( 1 );
return 0;
}
}
// Applies an operator to numbers.
long evaluate( char op, long x, long y )
{
// Based on the operator, perform the operation.
switch( op ) {
case '+':
return x + y;
case '-':
return x - y;
case '*':
return x * y;
case '/':
return x / y;
case '^':
return pow(x,y);
default:
cout << "Illegal operator" << endl;
exit( 1 );
return 0;
}
}
long pow(long x, long y){
if (y == 0){
return 1;
}else{
if (y == 1){
return x;
}else{
x = pow(x,y);
y-= 1;
return x;
}
}
}
|
