赞
踩
用二叉树来表示表达式,树的每一个节点包括一个运算符和运算数。代数表达式中只包含+,-,*,/,(,)和一位整数且没有错误。按照先括号,再乘除,后加减的规则构造二叉树。如图所示是"1+(2+3)*2-4/5"代数表达式对应二叉树,用对应的二叉树计算表达式的值。
输入格式:
输入一行表达式字符串,以#结束,括号内只能有一个运算符。
输出格式:
输出表达式的计算结果.
- #include<iostream>
- #include<stack>
- using namespace std;
- typedef struct node
- {
- char data;
- node* lchild, * rchild;
- }*tree;
- stack<tree> expt;
- int judge(char ch)//判断是运算符
- {
- if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#')
- return 1;
- else
- return 0;
- }
- int jisuan(int n1, int n2, char ch)//计算
- {
- if (ch == '+')
- return n1 + n2;
- else if (ch == '-')
- return n1 - n2;
- else if (ch == '*')
- return n1 * n2;
- else
- return n1 / n2;
- }
- char Precede(char ch1, char ch2)//判断优先级,ch1栈顶元素
- {
- char flag = '>';
- if (ch1 == '+')
- {
- switch (ch2)
- {
- case '+':
- case '-':
- case '#':
- case ')':
- flag = '>';
- break;
- case '*':
- case '/':
- case '(':
-
- flag = '<';
- break;
- }
- }
- else if (ch1 == '-')
- {
- switch (ch2)
- {
- case '+':
- case '-':
- case '#':
- flag = '>';
- break;
- case '*':
- case '/':
- case '(':
- case ')':
- flag = '<';
- break;
- }
- }
- else if (ch1 == '*')
- {
- switch (ch2)
- {
- case '+':
- case '-':
- case '#':
- case '*':
- case '/':
- case ')':
- flag = '>';
- break;
- case '(':
- flag = '<';
- break;
- }
- }
- else if (ch1 == '/')
- {
- switch (ch2)
- {
- case '+':
- case '-':
- case '#':
- case '*':
- case '/':
- case ')':
- flag = '>';
- break;
- case '(':
- flag = '<';
- break;
- }
- }
- else if (ch1 == '(')
- {
- switch (ch2)
- {
- case '+':
- case '-':
- case '*':
- case '/':
- case '(':
- flag = '<';
- break;
- case ')':
- flag = '=';
- break;
- }
- }
- else if (ch1 == ')')
- {
- switch (ch2)
- {
- case '+':
- case '-':
- case '*':
- case '/':
- case ')':
- case '#':
- flag = '>';
- break;
- }
- }
- else if (ch1 == '#')
- {
- switch (ch2)
- {
- case '+':
- case '-':
- case '*':
- case '/':
- case '(':
- flag = '<';
- break;
- case '#':
- flag = '=';
- break;
- }
- }
- return flag;
- }
- void create(tree& t, tree a, tree b, char ch)//构建子树
- {
- t = new node;
- t->data = ch;
- t->lchild = a, t->rchild = b;
- }
- void Createtree()
- {
- char ch;
- stack<char> optr;//运算符
- optr.push('#');
- cin >> ch;//输入
- while (ch != '#' || optr.top() != '#')
- {
- if (!judge(ch))//不是运算符
- {
- tree t;
- t = new node;
- create(t, NULL, NULL, ch);//构建子树,操作数的左右子树为空
- expt.push(t);//压入子树栈
- cin >> ch;
- }
- else
- {
- switch (Precede(optr.top(), ch))
- {
- case '<'://ch的优先级高于栈顶运算符
- optr.push(ch);//ch压入运算符栈
- cin >> ch;
- break;
- case '>'://栈顶运算符优先级高于ch
- char yun;
- yun = optr.top();//取栈顶运算符
- optr.pop();
- tree a, b;
- a = new node, b = new node;
- b = expt.top();//右子树
- expt.pop();
- a = expt.top();//左子树
- expt.pop();
- tree t;
- t = new node;
- create(t, a, b, yun);//以栈顶运算符为根,构建子树
- expt.push(t);
- break;
- case '=':
- optr.pop();
- cin >> ch;
- break;
- }
- }
-
- }
- }
- int valuetree(tree t)//树计算
- {
- int lchild = 0, rchild = 0;
- if (t->lchild == NULL && t->rchild == NULL)
- return t->data - '0';
- else
- {
- lchild = valuetree(t->lchild);
- rchild = valuetree(t->rchild);
- return jisuan(lchild, rchild, t->data);
- }
- }
- void printtree(tree t)//中序遍历
- {
- if (t)
- {
- printtree(t->lchild);
- cout << t->data;
- printtree(t->rchild);
-
- }
- }
- int main()
- {
- Createtree();
- tree t = expt.top();//栈底即为树
- //printtree(t);
- int a = valuetree(t);
- cout << a;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。