基于栈的中缀算术表达式求值

2019/10/29 23:34

#include<iostream>
#include<string>
#include<cstring>
#include<iomanip>
using namespace std;
typedef struct StackNode *LStack;
/*

*/
typedef struct Data {
double number;
char op;
};
struct StackNode {
Data data;
LStack next;
};
double Function(double a, double b, char op)
{
if (op == '+')
return a + b;
else
if (op == '-')
return b - a;
else
if (op == '*')
return b * a;
else
if (op == '/')
return b / a;
}
char Judge(char a, char b)
{
if ((a == '('&&b == ')') || (a == '='&&b == '='))//a\b都为等号？
return '=';
else
if (a == '(' || a == '=' || b == '(' || (a == '+' || a == '-') && (b == '*' || b == '/'))
return '<';
else
return '>';
}
void InitStack(LStack &s)
{
s = NULL;
}
void Creat1(LStack &s, double a)//数字
{
LStack p = new StackNode;
p->data.number = a;
p->next = s;
s = p;

}
void Creat2(LStack &s, char a)//op
{
LStack p = new StackNode;
p->data.op = a;
p->next = s;
s = p;

}
void Pop(LStack &s)
{
LStack q;
q = s;
s = s->next;
delete q;
}
double GetTop1(LStack &s)//number取栈顶元素
{
return s->data.number;
}
char GetTop2(LStack &s)//op
{
return s->data.op;
}
int  main()
{
string c;
double y;
while (1)
{
cin >> c;
if (c[0] == '=')
break;
LStack s1, s2;
InitStack(s1);//数字
InitStack(s2);//运算符
Creat2(s2, '=');
int x = 0, e = 0, flag = 0;//??
for (int i = 0; i < c.size(); i++)
{
if (c[i] >= '0' && c[i] <= '9')//还要考虑有小数点呢
{
flag = 1;
x = x * 10 + c[i] - '0';
if (e)
{
e *= 10;
}
}
else
if (c[i] == '.')
{
e = 1;
}
else
{
if (flag)
{
if (e)
{
y = x * 1.0 / e;
}
else
y = x * 1.0;
Creat1(s1, y);
x = 0;
e = 0;
flag = 0;
}
while (1)
{
if (Judge(GetTop2(s2), c[i]) == '<')
{
Creat2(s2, c[i]);
break;
}
else
if (Judge(GetTop2(s2), c[i]) == '>')
{
double a, b;
a = GetTop1(s1);
Pop(s1);
b = GetTop1(s1);
Pop(s1);
char op;
op = GetTop2(s2);
Pop(s2);
y = Function(a, b, op);
Creat1(s1, y);
}
else
{
Pop(s2);
break;
}

}
}

}
cout << setiosflags(ios::fixed) << setprecision(2);
cout << s1->data.number << endl;
}
return 0;

}

0
0 收藏

0 评论
0 收藏
0