问题:输入前缀表达式,输出计算结果
分析:
1.输入:对应infixExp的input函数,要保证能接受多位十进制数,我选用cin.peek()函数,对输入流中的下一个字符先peek,分类讨论,如果是符号,用cin输入一个数;如果是数字,再peek下一个字符,直到符号为止。
存储形式:如果要让符号和数字都在一个vector中存储,就需要自己编写一个类型,可以分别容纳符号和数字,对应MyNum类。
2.前缀转后缀:对应infixExp::toPostfixExp()函数,维护一个符号栈,根据符号的优先级,来维护这个符号栈。
存储形式:转换好的后缀表达式保存在PostFixExp类中。
3.后缀求值:对应Calculator类中的run()函数,维护一个数字栈。
代码如下:可以直接运行
(栈是自己实现的,也可以选用stl中的stack容器,稍加修改即可)
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const double e = 1E-7;
template <class T>
class Stack {
private:
int mSize;
int top;
T *st;
public:
Stack():mSize(0), top(-1), st(NULL) {}
Stack(int n): mSize(n), top(-1), st(new T[mSize]) {}
Stack(const Stack & s) {
if( s != this) {
delete [] st;
mSize = s.mSize;
top = -1;
st = new T[mSize];
}
else cout << "copy constructor false" << endl;
}
~Stack() { delete [] st;}
bool push(const T item);
bool pop(T &item);
bool getTop(T & item);
void clear() {top = -1;}
bool isEmpty() const {
return top == -1 ? true: false;
}
};
template <class T>
bool Stack<T>::push(const T item) {
if(top == mSize - 1) {
T * newSt = new T[mSize * 2];
for(int i = 0; i <= top; i++)
newSt[i] = st[i];
delete [] st;
st = newSt;
mSize *= 2;
}
st[++top] = item;
return true;
}
template <class T>
bool Stack<T>::pop(T & item) {
if(top == -1) {
cout << "栈为空,不能执行出栈操作" << endl;
return false;
}
item = st[top--];
return true;
}
template <class T>
bool Stack<T>::getTop(T & item) {
if(top == -1) {
cout << "栈为空,不能读取栈顶元素" << endl;
return false;
}
item = st[top];
return true;
}
// 以上栈实现完成
enum MyNumType {number, charactor, nothing};// 枚举类型,标志MyNum的类型
class MyNum {
private:
char c;
double d;
MyNumType flag ; // flag = 1(true), myNum = char;
// flag = 0(false), myNum = double;
public:
MyNum():flag(nothing) {}
explicit MyNum(char a):c(a), flag(charactor) {}
explicit MyNum(double a):d(a), flag(number) {}
friend ostream & operator << ( ostream & o, const MyNum num);
bool isDouble() const {
if(flag == MyNumType::number)
return true;
else
return false;
}
char getCharValue() const {
if(flag == MyNumType::charactor)
return c;
else {
cout << "the MyNum is not char!" << endl;
return '?';
}
}
double getDoubleValue() const {
if(flag == MyNumType::number)
return d;
else {
cout << "the MyNum is not double!" << endl;
return 0;
}
}
};
ostream & operator << ( ostream & o, const MyNum num) {
if (num.flag == MyNumType::charactor)
o << num.c;
else
o << num.d;
return o;
}
//以上MyNum类实现完成
class Calculator { //表达式求值
private:
Stack<double> s;
bool getTwoOperands(double& opd1, double& opd2);
void compute(char op);
public:
Calculator():s(50) {};
void run(const vector<MyNum> & v);
void clearElem() { s.clear();}
};
bool Calculator::getTwoOperands(double& opd1, double& opd2) {
if(s.isEmpty()) {
cerr << "Missing operand" << endl;
return false;
}
s.pop(opd2); // 后操作数
if(s.isEmpty()) {
cerr << "Missing operand!" << endl;
return false;
}
s.pop(opd1); // 前操作数
return true;
}
void Calculator::compute(char op) {
bool result;
double opd1, opd2; // opd1 is front of op, opd2 is after op
result = getTwoOperands(opd1, opd2);
if(result == true) {
switch(op) {
case '+': s.push(opd1 + opd2); break;
case '-': s.push(opd1 - opd2); break;
case '*': s.push(opd1 * opd2); break;
case '/':
if( -e <= opd2 && opd2 >= e ) {
s.push(opd1 / opd2);
}
else {
cout << "Divided by 0" << endl;
clearElem();
exit(1);
}
break;
}
}
else
clearElem();
}
void Calculator::run(const vector<MyNum> &v) {
char c;
double newOperand, res;
for(auto i: v) {
if(i.isDouble()) {
s.push(i.getDoubleValue() );
}
else {
c = i.getCharValue();
if(c == '=')
break;
else {
compute(c);
}
}
/*switch(i) {
case '+':
case '-':
case '*':
case '/':
compute(c);
break;
default:
cin.putback(c);
cin >> newOperand;
s.push(newOperand);
break;*/
}
if(s.pop(res))
cout << endl << "Result is " << res <<endl;
}
//以上Calculator类完成
class InfixExp {
private:
vector<MyNum> v;
Stack<char> opstack;
vector<MyNum> postfixExp;
bool opCompare(MyNum i);
public:
InfixExp();
~InfixExp() {} ;
vector<MyNum> input();
friend ostream & operator << ( ostream & o, const InfixExp & i );
vector<MyNum> toPostfixExp();
};
InfixExp::InfixExp():opstack(50){
v = input();
//opstack(50);
}
ostream & operator << ( ostream & o, const InfixExp & in) {
for(auto &i: in.v)
o << i;
return o;
}
vector<MyNum> InfixExp::input() {
double num;
char c;
vector<MyNum> v;
while(1) {
c = cin.peek();
if( c == ' ') {
cin.get();
continue;
}
if( c == '=') {
cin >> c;
v.push_back(MyNum(c) );
break;
}
else if( '0' <= c && c <= '9' ) {
cin >> num;
v.push_back(MyNum(num) );
}
else{
cin >> c;
v.push_back(MyNum(c) );
}
}
cout << "input done!" << endl;
return v;
}
ostream & operator << ( ostream & o, const vector<MyNum> v) {
for (auto i: v)
o << i << " ";
return o;
}
bool InfixExp::opCompare(MyNum i) {
//cout << "op: " << i ;
const char c = i.getCharValue();
if(c == '=') {
char ch;
while(!opstack.isEmpty()) {
opstack.pop(ch);
//cout << "before = is: " << ch << endl;
postfixExp.push_back(MyNum(ch) );
}
postfixExp.push_back(MyNum(c) );
//cout << "The final postfixexp is: " << postfixExp << endl;
return true;
}// end if
else if(c == ')') {
//cout << 1 << endl;
char ch = ')' ;
while(ch != '(') {
if(opstack.isEmpty()) {
cout << "the expression is illicit! "
<< "miss '(' " << endl;
exit(0);
}
opstack.pop(ch);
if(ch != '(' )
postfixExp.push_back(MyNum(ch) );
}
return true;
} // end else if
else if( opstack.isEmpty() || c == '(') {
//cout << 2 << endl;
opstack.push(c);
return true;
}// end else if
else {
//cout << 3 ;
char ch;
opstack.getTop(ch);
if(ch == '(') {
//cout << ".1" << endl;
opstack.push(c);
return true;
}
else {
//cout << ".2" ;
while(!opstack.isEmpty() ) {
if(ch == '(' ) {
//cout << 1 << endl;
opstack.push(c);
return true;
}
else if (ch == '*' || ch == '/') {
//cout << 2 << endl;
opstack.pop(ch);
postfixExp.push_back(MyNum(ch) );
}
else if (ch == '+' || ch == '-') {
//cout << 3 << endl;
if(c == '*' || c == '/') {
opstack.push(c );
return true;
}
else {
opstack.pop(ch);
postfixExp.push_back(MyNum(ch) );
}
}
if(opstack.isEmpty()) {
opstack.push(c);
return true;
}
opstack.getTop(ch);
}
opstack.push(c);
return true;
}// end inner else
}//else
}// end function
vector<MyNum> InfixExp::toPostfixExp() {
for(auto i: v) {
//cout << "the current postfixExp is: " << postfixExp << endl;
//cout << i << endl; // 这里我加了一个调试信息,从这里下手开始调试,可能时Stack的错误,必要时全部换成标准库中的stack
if(i.isDouble() == true) {
//cout << "number:" << i << endl;
postfixExp.push_back(i);
}
else
opCompare(i);
}
return postfixExp;
}
//以上infixExp类完成
class PostfixExp {
private:
vector<MyNum> postfixExp;
public:
PostfixExp(vector<MyNum> v):postfixExp(v) {}
const vector<MyNum> getPostfixExp() const {
return postfixExp;
}
};
int main() {
InfixExp infixExp;
cout << "infixexp is: " << infixExp << endl;
cout << "postfixexp is: " << infixExp.toPostfixExp() << endl;
PostfixExp postfixExp( infixExp.toPostfixExp() );
Calculator c;
c.run(postfixExp.getPostfixExp() );
return 0;
}