#include
#include
using namespace std;
#define Stack_Size 100
typedef char ElemType;
typedef struct {
char elem[Stack_Size];
int top;
}SqStack;
void InitStack(SqStack &S) { //初始化顺序栈
// S.elem = new ElemType[Stack_Size];
S = (SqStack)malloc(sizeof(SqStack));
S->top = -1;
}
bool Push(SqStack *&S, char c) { //顺序栈压栈
// if (S.top == (Stack_Size - 1)) Error("Stack Overflow!");
// S.elem[++S.top] = c;
if (S->top == Stack_Size - 1)return false;
S->top++;
S->elem[S->top] = c;
return true;
}
ElemType Pop(SqStack *&S) { //顺序栈出栈
// if (S.top == -1) Error("Stack Empty!");
if (S->top == - 1)return NULL;
S->top--;
ElemType e = S->elem[S->top];
return e;
}
int StackLength(SqStack &S) { //求顺序栈长度
return (S.top + 1);
}
ElemType GetTop(SqStack *&S) { //取栈顶元素 e=S.elem[top];
return S->elem[S->top];
}
typedef struct{ //动态顺序串
char *ch;
int length;
}String;
int StrLength(String &S) { //求串长
return S.length;
}
void StrNeg(String &S, String &F) { //求逆序串
if (!S.length) //error(“String Empty!”);
for (int i = 0; i < S.length; i++)
F.ch[i] = S.ch[S.length - 1 - i];
}
typedef struct TNode{ //二叉树结点
union data{
char optr; //运算符
int opnd;
}data; //操作数
struct TNode lchild, *rchild;
}BiTree;
int Precedence(char opr) { //判断运算符级别函数;其中 /的级别为2,+ -的级别为1;
int level;
switch (opr) {
case'+': case'-': return (1); break;
case'*': case'/': return(2); break;
case'(': case')':
case'#':
default:
return(0); break;
}
}
bool IsOperator(char opr) { //判断输入串中的字符是不是合法操作符
if (opr == '+' || opr == '-' || opr == '*' || opr== '/')
return true;
else
return false;
}
//bool IsOperand(char opr){
//
//}
bool IsDigit(char opr){
if (opr >= 48 && opr <= 57)
return true;
return false;
}
String Convert(String Str) { //将一个中缀串转换为后缀串,
String Output; //输出串
//Output.ch = "";
Output.ch=new char(Str.length);
Output.length = 0;
SqStack S;
InitStack(S);
ElemType e;
for (int i = Str.length - 1; i >= 0; i--) { //对输入串逆序扫描
if (Str.ch[i] >= 48 && Str.ch[i] <= 57) {
//Output.ch[i] = Str.ch[i]; //假如是操作数,把它添加到输出串中。
Output.ch[Output.length] = Str.ch[i];
Output.length++;
}
if (Str.ch[i] == ')') //假如是右括号,将它压栈。
Push(S, Str.ch[i]);
while (IsOperator(Str.ch[i])) { //如果是运算符
if (S->top == 0 || GetTop(S) == ')' || Precedence(Str.ch[i]) >= Precedence(GetTop(S))) {
Push(S, Str.ch[i]);
break;
}
else {
e = Pop(S);
Output.ch[i] = e;
Output.length++;
}
}
if (Str.ch[i] == '(') { //假如是左括号,栈中运算符逐个出栈并输出,直到遇到右括号。右括号出栈并丢弃。
while (GetTop(S) != ')') {
Output.ch[i] = Pop(S);
Output.length++;
}
}
}
while (S->top != -1) { //假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。 Output.ch=Output.ch--;
Output.ch[S->top] = Pop(S);
}
return Output;
}
void CreatBiTree(BiTree *&T, String &S) { //由中缀表达式生成表达式二叉树
String F;
SqStack *Sq; //用以存放生成的二叉树结点
InitStack(Sq);
F = Convert(S); //求得S的前缀表达式
for (int i = F.length - 1; i >= 0; i--) {
if(!IsOperator(F.ch[i])) {
T = new TNode;
T->data.optr = F.ch[i];
T->lchild = NULL;
T->rchild = NULL;
Push(Sq, T->data.optr);
}
else {
T = new TNode;
T->data.optr = F.ch[i];
T->lchild->data.optr = Pop(Sq);
T->rchild->data.optr = Pop(Sq);
Push(Sq, T->data.optr);
}
}
}
int Calc(int a, char opr, int b) { //计算
switch (opr) {
case '+': return a + b;
case '-': return a - b;
case '': return a * b;
case '/': return a / b;
}
}
int Value(TNode *T) {
if (T->lchild == NULL &&T->rchild == NULL)
return T->data.opnd;
else
return Calc(Value(T->lchild), T->data.opnd, Value(T->rchild));
};
void Face() //输出简单界面即信息
{
cout << " ※※※※※※※※※※※※ " << endl;
cout << " ※ 十进制计算器 ※ " << endl;
cout << " ※※※※※※※※※※※※ " << endl;
cout << " 试验1406 欧阳玲玲 " << endl;
}
bool JudegExp(String Exp) //此函数验证式子是否正确,即是否符合运算规则。
{
char check;
int error = 0;
int lb = 0;
int rb = 0;
if (StrLength(Exp) == 1 && Exp.ch[0] != '-')
return false;
else if ((IsOperator(Exp.ch[0]) && Exp.ch[0] != '-' || IsOperator(Exp.ch[StrLength(Exp) - 1])) && Exp.ch[0] != '(' && Exp.ch[StrLength(Exp) - 1] != ')') //此处若不加,在遇到某些式子时,会出现非法操作。
return false;
for (int m = 0; m < StrLength(Exp); m++)
{
check = Exp.ch[m];
if (m == 0 && check == '-' && (IsDigit(Exp.ch[1]) != 0 || Exp.ch[1] == '('))
check = Exp.ch[++m];
if (IsDigit(check)); //如果是数字,跳过,不管。
else if(IsOperator(check))
{
if (check == ')')
{
rb++; if (IsOperator(Exp.ch[m + 1]) && (Exp.ch[m + 1] == '+' || Exp.ch[m + 1] == '-' || Exp.ch[m + 1] == '*' || Exp.ch[m + 1] == '/' || Exp.ch[m + 1] == '^' || Exp.ch[m + 1] == ')'))
{
m++;
if (Exp.ch[m] == ')')
rb++;
}
else if (IsOperator(Exp.ch[m + 1]))
error++;
}
else if (check == '(')
{
lb++;
if (Exp.ch[m + 1] == '(')
{
m++;
lb++;
}
else if (IsOperator(Exp.ch[m + 1]) && Exp.ch[m + 1] != '-')
error++;
}
else
{
if (IsOperator(Exp.ch[m + 1]) && Exp.ch[m + 1] == '(')
{
m++;
lb++;
}
else if (IsOperator(Exp.ch[m + 1]))
error++;
}
}
else error++;
}
if (error == 0 && lb == rb)
return(true);
else
return(false);
}
void main() {
int N;
char e;
int flag;
String S;
string Str;
BiTree *T;
SqStack *L;
Face();
S.ch = ""; //输出界面及相关信息
do {
cout << "Please input an expression : " << endl;
S.ch = "1+2+3*7#";
S.length=strlen(S.ch)-1;
InitStack(L);
JudegExp(S); //判断输入的表达式是否合法。
CreatBiTree(T,S);
N = Value(T);
cout << "The value of this expression is”"<< N << endl;
cout << "To do another calculation ? [Y / N]";
cin >> e;
if (e == 'y') flag = 1;
else flag = 0;
} while (flag);
}//main