数据结构，用逆波兰表达式求四则混合运算的值，使用C/C++

Question

利用逆波兰表达式求一个四则混合元算的值。
具体要求：
1、 定义二叉树的型BTREE和位置的型position。
2、 实现二叉树的基本操作。
3、 实现将一个四则混合运算转换成二叉树的函数：BTREEconvert(char *express)，其中参数express为四则混合运算表达式，返回值为生成的树。
4、 实现计算四则混合运算的值的函数：doublecomputer(BTREE bt)，其中，参数bt为四则运算所对应的树，返回值为计算结果。提示：先求树的的波兰表达式，然后利用栈结构计算表达式的值。
在主函数中进行测试，求2+3*（5+8）/4-5的值。

Answer 1

你可以直接利栈来写吧！将中缀表达式转换成后缀表达式！

然后还是利用栈来计算！这个二叉树递归来递归去搞得人都不好了！

将中缀表达式转换为后缀表达式的搞法：

与栈顶元素比较

优先级高的进栈

否者出栈到后缀表达式中

表达式中有+，-*,/（ )

现在我们来看他们的优先级

毋庸置疑括号的优先级最高

所以‘（' 进栈,

当字符为')'时

只要栈顶元素不等于’（‘就出栈

然后跳过括号

只剩下加减乘除的运算符了

那么+-的级别最低

所以直接把前面的字符出栈，

然后再把现在的加或者减运算符入栈

*/时因为这两个的优先级高所以

栈顶元素等于* /时出栈

直到栈顶元素优先级比

*/小 时  *或者/进栈

数字字符直接输出

#define MaxLen 1000
void GetExp(char *str,char*exp)
{
     struct stack
      {
        char data[MaxLen];
        int top;
        }s;
        s.top=-1;
        char ch=str[0];
        int i=1，t=0;
        while(ch!='\0')
        {
           switch(ch)
           {
             case '(':
                 s.top++;
                 s.data[s.top]=ch;
                 break;
             case ')':
             while(s.data[s.top]!='(')
             {
                 exp[t]=s.data[s.top];
                 s.top--;
                 t++;
                
             }
             s.top--;//跳过括号
             break;
           case' ':
              break;
            case'+':
            case'-':
            while(s.top！=-1&&s.data[s.top]!='(')
            {
               exp[t]=s.data[s.top];
               s.top--;
               t++;
            }
            s.top++;
            s.data[s.top]=ch;
            break;
           case'*':
           case'/':
           while(s.data[s.top]=='*'||s.data[s.top])=='/')
           {
                exp[t]=s.data[s.top];
                s.top--;
                t++;
           }
           s.top++;
           s.data[s.top]=ch;
           break;
           default:
           while(ch>='0'&&ch<='9')
           {
              exp[t]=ch;
              t++;
              ch=str[i];
              i++;
           }
           i--;
           exp[t]='#';
           t++;
           }
           ch=str[i];
           i++;
        }
        while(s.top!=-1)
        {
          exp[t]=s.data[s.top];
          s.top--;
          t++;
        }

     
}