程式師世界 >> 編程語言 >> 更多編程語言 >> 編程綜合問答 >> 但是存在了一點問題-數據結構課程設計：十進制二叉樹四則運算計算器設計與實現

但是存在了一點問題-數據結構課程設計：十進制二叉樹四則運算計算器設計與實現

編輯：編程綜合問答

數據結構課程設計：十進制二叉樹四則運算計算器設計與實現

#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