forked from ucsb-cs24-w22/lab06_data
-
Notifications
You must be signed in to change notification settings - Fork 3
/
evalfull.cpp
155 lines (128 loc) · 4.75 KB
/
evalfull.cpp
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
// evalfull.cpp - evaluates a fully-parenthesized expression
// NAME(S), DATE
#include <cstdlib> // for atof function
#include <cstdio> // for sscanf
#include <cstring> // for strcmp and strtok
#include <iostream>
#include <stack> // STL stack class
#include <string> // for throwing string exceptions
using namespace std;
// constants used to identify a token - DO NOT CHANGE
enum TokenType {LEFT, RIGHT, ADD, SUBTRACT, MULTIPLY,
DIVIDE, NUMBER, OTHER};
TokenType identify(char *t);
// balanced - returns true only if parentheses are balanced
// in the expression, where expression is an array of C
// string tokens like { "(", "4.2", ")" } and numTokens
// is the number of tokens in the array (3 in the sample)
bool balanced(char *expression[], int numTokens) {
stack<char *> s; // USE s TO SOLVE THE PROBLEM - it is an STL
// (Standard Template Library) structure with
// all of the same operations as the stack from
// Step 2 of this lab, but it won't get full
// and it can store any type - <char *> here
return false; // REPLACE THIS return WITH ACTUAL IMPLEMENTATION
}
// DO NOT CHANGE ANYTHING BELOW - BUT DO READ IT
// utility function returns one of those constants
TokenType identify(char *t) {
if (strcmp(t, "(") == 0)
return LEFT;
if (strcmp(t, ")") == 0)
return RIGHT;
if (strcmp(t, "+") == 0)
return ADD;
if (strcmp(t, "-") == 0)
return SUBTRACT;
if (strcmp(t, "*") == 0)
return MULTIPLY;
if (strcmp(t, "/") == 0)
return DIVIDE;
float value;
if (sscanf(t, "%g", &value) == 1)
return NUMBER;
return OTHER;
}
// evalFull - evaluates a fully-parenthesized expression;
// relies on function balanced;
// returns result of the expression if it is formed properly
// throws string message if expression is not proper
double evalFull(char *expression[], int numTokens) {
if ( !balanced(expression, numTokens) )
throw string("parentheses are not balanced");
stack<double> numbers;
stack<TokenType> ops;
double result = 0, leftValue, rightValue;
TokenType type, op;
for (int i=0; i<numTokens; i++) {
type = identify(expression[i]);
switch(type) {
case NUMBER:
numbers.push( atof(expression[i]) );
break;
case ADD: case SUBTRACT: case MULTIPLY: case DIVIDE:
ops.push(type);
break;
case LEFT:
break; // ignore left paren (know balanced already)
case RIGHT:
if (numbers.empty())
throw string("empty stack where two numbers expected");
rightValue = numbers.top();
numbers.pop();
if (ops.empty())
throw string("empty stack where operator expected");
op = ops.top();
ops.pop();
if (numbers.empty())
throw string("empty stack where one number expected");
leftValue = numbers.top();
numbers.pop();
if (op == ADD)
numbers.push(leftValue + rightValue);
else if (op == SUBTRACT)
numbers.push(leftValue - rightValue);
else if (op == MULTIPLY)
numbers.push(leftValue * rightValue);
else // op == DIVIDE
numbers.push(leftValue / rightValue);
break; // end right paren case
default:
throw string("unknown token: ")
+ string(expression[i]);
}
}
if (!ops.empty())
throw string("operator(s) left on stack at end");
if (numbers.empty())
throw string("empty stack where one result should be");
result = numbers.top();
numbers.pop();
if (!numbers.empty())
throw string("number(s) left on stack at end");
return result;
}
#define MAXLEN 100
// main gets expression from user and evaluates it
int main() {
char input[MAXLEN], *tokens[MAXLEN/2];
cout << "enter expression: ";
cin.getline(input, MAXLEN);
// ( ( 4.2 * 6.4 ) + 5 )
char *ptr = strtok(input, " ");
int count = 0;
while (ptr != 0) {
tokens[count] = ptr;
++count;
ptr = strtok(0, " ");
}
try {
double result = evalFull(tokens, count);
cout << "result: " << result << endl;
}
catch(string error) {
cerr << "bad expression: " << error << endl;
return 1;
}
return 0;
}