数据结构课程设计:十进制二叉树四则运算计算器设计与实现

#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

1个回答

调试下看看呢,是不是代码不正确

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问