精华内容
下载资源
问答
  • 关于表达式求值的数据结构代码,程序采用栈结构实现表达式输入和输出及求值,输出结果是中缀表达式和算式的正确结果
  • 请设计程序将中缀表达式转换为后缀表达式。 输入格式: 输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。 输出格式: 在一行中输出转换后的后缀表达式,要求不同对象...

    表达式转换

    算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

    输入格式:
    输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。

    输出格式:
    在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。

    输入样例:

    2+3*(7-4)+8/4

    输出样例:

    2 3 7 4 - * + 8 4 / +

    知识点:将中缀表达式转化为后缀表达式:
    两种情况:
    (1)没有括号的中缀表达式转化为后缀表达式:

    没有括号的中缀表达式转化为后缀表达式
    (2)带有括号的中缀表达式转化为后缀表达式:

    带有括号的中缀表达式转化为后缀表达式
    分析:本题是带有括号的中缀表达式,需要利用第二种方式实现,模拟过程我会在代码上详解
    这里说一下这道题的细节问题:
    中缀表达式转换为后缀表达式:对于本题而言,细节过多,在完成表达式转换的基础上
    1.需要控制空格,首尾不能出现空格
    2.需要判断一位以上的数字之间不能有空格
    3.需要判断小数的情况,注意之间不能有空格
    4.需要判断镶嵌括号的情况,容易出现格式错误
    例如:当一开始就输入多个空格会使首位出现空格
    5.需要判断正负号
    (1)对于正号,当出现在第一位时需直接特判(在第一位无需加括号)
    未在第一位出现正号一定会在括号内,而且输出时正号要省略
    (2)对于负号,当出现在第一位时需要直接特判(在第一位出现无需加括号)
    未在第一位出现负号一定会在括号内,需要输出负号
    (3)注意控制好空格,防止格式错误

    下面是代码:

    
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<stack>
    #include<algorithm>
    using namespace std;
    const int M=1010;
    char str[M],st[M],c;
    stack<char> q;
    int main()
    {
        int i,j,k=0,l,m,n,f=0,t=0,ff=0;
        cin.getline(str,110);
        l=strlen(str);
        for(i=0; i<l; i++)
        {
            if(str[i]>='0'&&str[i]<='9')///为数字时输出
            {
                t=1;///标记已经出现过数字
                ///解决当有镶嵌括号时的格式问题
                if(ff==0)///特判当刚开始有镶嵌括号时防止f=1对格式的影响
                {
                    printf("%c",str[i]);
                    ff=1;
                    f=0;
                    continue;
                }
                ///解决超过一位数的问题
                if(f==0)///遇到数字并且前一个也是数字或'.'输出
                    printf("%c",str[i]);
                else ///f=1时遇到数字加空格输出,并使f=0
                {
                    printf(" %c",str[i]);
                    f=0;
                }
            }
            ///解决小数问题
            else if(str[i]=='.')///遇到点说明为小数直接输出
            {
                printf("%c",str[i]);
            }
            ///解决第一位为正数带'+'的问题
            else if(i==0&&str[i]=='+')
            {
                printf("%c",str[i]);
            }
            ///解决第一位为正数带'-'的问题
            else if(i==0&&str[i]=='-')
            {
                printf("%c",str[i]);
            }
            ///解决非第一位为正数带'-'的问题
            else if(str[i]=='('&&str[i+1]=='-')
            {
                ///输出符号
                if(t==1)///若已经出现数字,加符号时需在前面加空格
                    printf(" %c",str[i+1]);
                else
                    printf("%c",str[i+1]);
                q.push(str[i]);///将括号入栈
                f=0;///输出数字无需加空格
                i++;///跳过这个'-'
            }
            ///解决非第一位为正数带'+'的问题
            else if(str[i]=='('&&str[i+1]=='+')
            {
                ///带正号的数字的正号可以约去
                q.push(str[i]);///将括号入栈
                f=1;///输入数字时需要加空格
                i++;///跳过'+'
            }
            ///当遇见左括号
            else if(str[i]=='(')
            {
                q.push(str[i]);///放入栈中
                f=1;
            }
            ///遇见右括号
            else if(str[i]==')')
            {
                ///输出左括号到右括号之间的符号
                while(q.top()!='(')
                {
                    printf(" %c",q.top());
                    f=1;///当输入数字时需加空格
                    q.pop();///将输出的字符出栈
                }
                //printf("%c\n",q.top());
                q.pop();///将左括号出栈
            }
            else
            {
                ///当栈为空或者栈顶元素为左括号
                if(q.size()==0||q.top()=='(')
                {
                    f=1;///输入数字时需要加空格
                    q.push(str[i]);///将符号放入栈中
                }
                ///当需要入栈的符号优先级大于栈顶符号优先级
                else if((str[i]=='*'||str[i]=='/')&&(q.top()=='+'||q.top()=='-'))
                {
                    f=1;///输入数字时需加括号
                    q.push(str[i]);///将符号入栈
                }
                ///入栈的符号优先级小于或等于栈顶符号优先级
                ///栈中元素不为空且栈顶元素不是左括号
                else
                {
                    ///当栈顶元素为'*'或'/'
                    if(q.top()=='*'||q.top()=='/')
                    {
                        f=1;///输入数字需加空格
                        printf(" %c",q.top());///加空格输出栈顶元素
                        q.pop();///将栈顶元素出栈
                        ///出栈完看栈中元素是否为空
                        
                        ///此时四种情况
                        ///(1)栈中元素为0
                        ///(2)栈顶元素为'('
                        ///(3)栈底元素为'+'或'-',输入符号为'*'或'/'
                        ///(4)栈底元素为'+'或'-',输入符号为'+'或'-'
                        
                        ///情况一和情况二
                        if(q.size()==0||q.top()=='(')
                        {
                            f=1;///输出数字时需加空格
                            q.push(str[i]);///将符号放入栈中
                        }
                        ///情况三
                        else if(str[i]=='*'||str[i]=='/')
                        {
                            f=1;///输出数字时需加空格
                            q.push(str[i]);///直接将符号入栈
                        }
                        ///情况四
                        else if(str[i]=='+'||str[i]=='-')
                        {
                            f=1;///输出数字时需加空格
                            printf(" %c",q.top());///将栈顶元素加空格输出
                            q.pop();///栈顶元素出栈
                            q.push(str[i]);///将符号放入栈中
                        }
                    }
                    ///当栈顶元素为'+'或'-'
                    else if(q.top()=='+'||q.top()=='-')
                    {
                        ///两种情况
                        ///(1)入栈符号为'*'或'/'
                        ///(2)入栈符号为'+'或'-'
                        
                        ///情况一
                        if(str[i]=='*'||str[i]=='/')
                        {
                            f=1;///输出数字时需加空格
                            q.push(str[i]);///将符号放入栈中
                        }
                        else if(str[i]=='+'||str[i]=='-')
                        {
                            f=1;///输出数字时需加空格
                            printf(" %c",q.top());///输出栈顶元素
                            q.pop();///栈顶元素出栈
                            q.push(str[i]);///将符号放入栈中
                        }
                    }
                }
            }
        }
        ///当栈中符号未完全出栈
        while(q.size()!=0)
        {
            printf(" %c",q.top());///将栈中符号依次输出
            q.pop();///依次出栈
        }
        printf("\n");
        return 0;
    }
    
    
    
    展开全文
  •  现在使用树这一数据结构来将后缀表达式还原为中缀表达式.使用的是表达式树.表达式树是二叉树的一种,所谓二叉树,要么它为为空树,要么不空树,并且每个节点最多有两个孩子.而表达式树则是二叉树的一种,它的叶节点...

      在前面的文章中,使用了栈这一数据结构将通常使用的中缀表达式转换成了后缀表达式,并再一次使用栈来对后缀表达式求值,从而计算出了表达式的值.

      现在使用树这一数据结构来将后缀表达式还原为中缀表达式.使用的是表达式树.表达式树是二叉树的一种,所谓二叉树,要么它为为空树,要么不为空树,并且每个节点最多有两个孩子.而表达式树则是二叉树的一种,它的叶节点全为表达式中的数字,其余节点是运算符,即加,减,乘,除的运算符号.如图所示,就是一棵表达式树:

     

      它的特点显而易见.若我们对其进行先序遍历(preorder),将获得该表达式的前缀版本(前缀表达式):-+3*29/64;对其中序遍历(inorder),得到中缀表达式:3+2*9-6/4;对其后序遍历(postorder),得到后缀表达式:329*+64/-.

      通过给出某个版本的表达式,可以构建一棵该表达式所对应的表达式树.以后缀表达式为例,树节点的结构如下:

    1 struct  EtreeNode
    2 {
    3     char value;            //节点的值
    4     EtreeNode *left;     //指向左孩子   
    5     EtreeNode *right;  //指向右孩子
    6 };    

      构造一棵表达式树,需要用到栈.算法与后缀表达式求值的算法很相似.若输入是一个数字,创建一个节点指针,保存该数字,左右孩子指针皆为空(nullptr),将该节点指针压栈;若输入是运算符号,同样的申请空间建立节点指针保存它,再从栈中弹出两个节点指针作为该指针的左右孩子域.依次进行,直到输入完结,弹栈,得到的是对应的表达式树的根节点.

      C++实现如下:

     1 EtreeNode* creat_etree(const string &in)           //构建表达式树
     2 {
     3     if (!isdigit(in.at(0)))                                            //第一个输入若为运算符
     4     {
     5         try
     6         {
     7             ;
     8             throw runtime_error("illegal expression");
     9         }
    10 
    11         catch (runtime_error err)
    12         {
    13             cout << err.what() << endl;
    14             exit(EXIT_FAILURE);
    15         }                                                                        //第一个输入若为运算符,抛出异常,程序结束运行
    16     }
    17 
    18     stack <EtreeNode*> ptrStack;                                //保存节点指针的栈
    19 
    20     for (auto &i : in)                                                    //遍历整个输入字符串
    21     {
    22         if (isdigit(i))                                                        //若为数字
    23         {
    24             EtreeNode *ptr = new EtreeNode;
    25             ptr ->value = i;
    26             ptr ->left = ptr ->right = nullptr;
    27             ptrStack.push(ptr);                                        //保存该数字并压栈
    28         }
    29 
    30         else                                                                    //为运算符
    31         {
    32             EtreeNode *b = ptrStack.top();
    33             ptrStack.pop();
    34 
    35             EtreeNode *a = ptrStack.top();
    36             ptrStack.pop();                                                //弹出两个数字
    37 
    38             EtreeNode *ptr = new EtreeNode;
    39 
    40             ptr ->value = i;
    41             ptr ->left = a;
    42             ptr ->right = b;
    43             ptrStack.push(ptr);                                        //指针指向两个数字并压栈
    44         }
    45     }
    46 
    47     EtreeNode *root = ptrStack.top();                            //弹出根节点
    48     ptrStack.pop();
    49 
    50     return root;
    51 }

      这样,表达式树构建完成,其根节点指针为root,通过其即可访问整课表达式树.需要什么版本的表达式,就对其进行相应的遍历.如进行中序遍历得到中缀表达式:

     1 void inorder_traversal(EtreeNode *r)        //递归进行中序遍历
     2 {
     3     if (r == nullptr)
     4         return;
     5 
     6     else
     7     {
     8         inorder_traversal(r ->left);                //引用左子树
     9         cout << r ->value;                        //引用根节点
    10         inorder_traversal(r ->right);            //引用右子树
    11     }
    12 }

      这也是一种将后缀表达式转换为中缀表达式的方法.

    本人原创,谢谢大家!转载请注明出处,谢谢合作!

      

    转载于:https://www.cnblogs.com/Agent-YRBlogs/p/6030764.html

    展开全文
  • Infix expression invert to Reverse Polish expression前缀表达式(Polish expression, 波兰表达式)中缀表达式(Infix expression)后缀表达式(Reverse Polish expression, 逆波兰表达式)中缀表达式(Infix expression...

    前缀表达式(Polish expression, 波兰表达式)

    • 前缀表达式的运算符位于操作数之前 如中缀表达式(3+4)7-5的前缀表达式是 -+3475
    • 运算过程: 从右往左扫描表达式, 将数字按5,7,4,3的顺序压入栈中, 读到运算符+时弹出两个数(3和4), 运算后, 再将结果7压入栈内, 再读到运算符时弹出两个数(77), 运算后, 再将结果49压入栈内, 再读到运算符-时弹出两个数(49-5), 运算后, 再将结果44压入栈内, 即完成运算
      * 前缀表达式的运算顺序已经规划好了, 因此无需判断运算符的优先级

    中缀表达式(Infix expression)

    • 中缀表达式就是最常见的运算表达式 如 (3+4)*7-5. 此表达式需判断运算符的优先级

    后缀表达式(Reverse Polish expression, 逆波兰表达式)

    • 与前缀表达式相似, 只是运算符位于操作数后面 如中缀表达式(3+4)7-5的后缀表达式是 34+75-
    • 运算过程: 从左往右扫描表达式, 将数字3,4压入栈中, 读到运算符+时弹出两个数(3和4), 运算后, 再将结果7压入栈内, 再下一个数字7压入栈内, 再读到运算符时弹出两个数(77), 运算后, 再将结果49压入栈内, 再继续将下一个数字5压入栈内, 再读到运算符-时弹出两个数(49-5), 运算后, 再将结果44压入栈内, 即完成运算

    中缀表达式(Infix expression): 实现简单计算器

    • 思路分析
    1. 定义两个栈: 一个是数值栈, 另一个运算符栈
    2. 定义两个方法: 判断运算符优先级的方法和计算已入栈数值的方法
    3. 逐个循环扫描输入的中缀表达式, 如果是数字就入数值栈, 如果是运算符, 则需要与运算符栈的栈顶运算符比较优先级. 如果优先级高于栈顶的运算符, 则直接入栈(运算符栈), 否则, 从数值栈取2元素(数值), 在从运算符栈取栈顶元素做运算, 将运算结果再存入数值栈, 之后将当前运算符入栈(运算符栈)
    • 实例代码:
    
    /** 定义数组栈*/
    class ArrayStack {
        /** 栈大小*/
        private int maxSize;
        /** 通过该数组存放数据, 模拟栈数据结构*/
        private int[] stack;
        /** 栈顶的 index, 初始值为-1*/
        private int top = -1;
    
        public ArrayStack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[maxSize];
        }
    
        /** 栈满*/
        public boolean isFull() {
            return top == maxSize - 1;
        }
    
        /** 栈空*/
        public boolean isEmpty() {
            return top == -1;
        }
    
        /** 入/压栈*/
        public void push(int value) {
            if (isFull()) {
                System.out.println("入栈失败, 栈已满!");
                return;
            }
            top++;
            stack[top] = value;
        }
    
        /** 出/弹栈*/
        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("出栈失败, 没有数据!");
            }
            int value = stack[top];
            top--;
            return value;
        }
    
        /** 从栈顶开始打印所有内容*/
        public void list() {
            if (isEmpty()) {
                System.out.println("打印失败, 没有数据!");
                return;
            }
            for (int i = top; i >= 0; i--) {
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }
        }
    
        /** 查看栈顶元素内容*/
        public int peek() {
            return stack[top];
        }
    
        /** 运算符的优先级*/
        public int operPriority(int oper) {
            if (oper == '*'|| oper == '/') {
                return 1;
            } else if(oper == '+'|| oper == '-') {
                return 0;
            } else {
                /** 无效的表达式*/
                return -1;
            }
        }
    
        /** 判断是不是一个运算符*/
        public boolean isOper(char val) {
            return val == '+' || val=='-' || val=='*' || val=='/';
        }
    
        /** 计算方法*/
        public int cal(int num1, int num2, int oper) {
            int res = 0;
            switch (oper) {
                case '+':
                    res = num1 + num2;
                    break;
                case '-':
                    res = num2 - num1;
                    break;
                case '*':
                    res = num1 * num2;
                    break;
                case '/':
                    res = num2 / num1;
                    break;
                default:
                    break;
            }
            return res;
        }
    }
    
    public class CalculatorApp {
        public static void main(String[] args) {
            System.out.println("请输入要计算的中缀表达式: ");
            Scanner in = new Scanner(System.in);
            String expression = in.nextLine();
            in.close();
    
            /** 定义数值栈*/
            ArrayStack numStack = new ArrayStack(10);
            /** 定义运算符栈*/
            ArrayStack operStack = new ArrayStack(10);
    
            /** 表达式每个字符位索引*/
            int index = 0;
            /** 每次循环获取到的字符*/
            char ch;
            /** 计算多位数时, 用于拼接的字符串变量*/
            String keepnum = "";
            /** 当计算时, 从数值栈出栈的第一个数值*/
            int num1 = 0;
            /** 当计算时, 从数值栈出栈的第而二个数值*/
            int num2 = 0;
            /** 运算符 char <-> int*/
            int oper = 0;
            /** 计算结果*/
            int res = 0;
            while (true) {
                /** 每次循环获取单个字符*/
                ch = expression.substring(index, index + 1).charAt(0);
                /** 判断是否为运算符*/
                if (operStack.isOper(ch)) {
                    if (operStack.isEmpty()) {
                        /** 如果定义运算符栈为空, 直接入栈*/
                        operStack.push(ch);
                    } else {
                        /** 判断当前运算符(如 +)的优先级是否低于栈顶运算符(如 x), 如果低或相等通过*/
                        if (operStack.operPriority(ch) <= operStack.operPriority(operStack.peek())) {
                            /** 之前已入栈的数值与运算符取出, 开始计算*/
                            num1 = numStack.pop();
                            num2 = numStack.pop();
                            oper = operStack.pop();
                            res = operStack.cal(num1, num2, oper);
                            /** 数值栈的累计值计算后, 将值重新入栈*/
                            numStack.push(res);
                            /** 当前运算符(如 +), 入栈*/
                            operStack.push(ch);
                        } else {
                            operStack.push(ch);
                        }
                    }
                } else {
                    /**
                     * 1. 如果计算器只做单数的运算, 可以直接入栈 numStack.push(ch - 48);
                     * 2. 如果支持多位数, 需要往下一位判断是否为数值而不是运算符. 如果下一位是运算符就可以 numStack.push(keepnum)
                     * */
    
                    /** 循环拼接多位数( 如 12, 2, 6, 123)*/
                    keepnum += ch;
    
                    /** 如果是最后一位, 不再做下一位字符的判断*/
                    if (index == expression.length() - 1) {
                        numStack.push(Integer.parseInt(keepnum));
                    } else {
                        if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                            /** 如果下一位是运算符就入栈*/
                            numStack.push(Integer.parseInt(keepnum));
                            /** 清空数*/
                            keepnum = "";
                        }
                    }
                }
    
                index++;
                if (index >= expression.length()) {
                    /** 最后位, 停止循环*/
                    break;
                }
            }
    
            while (true) {
                /** 运算符栈为空时, 则计算结束停止循环*/
                if (operStack.isEmpty()) {
                    break;
                }
                num1 = numStack.pop();
                num2 = numStack.pop();
                oper = operStack.pop();
                res = operStack.cal(num1, num2, oper);
                numStack.push(res);
            }
    
            System.out.printf("%s的结算结构为 %d\n",expression, numStack.pop());
        }
    
    }
    
    输出:
    > 请输入要计算的中缀表达式: 
    > 12+2*6-123
    > 12+2*6-123的结算结构为 -99
    
    

    后缀表达式(Reverse Polish expression, 逆波兰表达式): 实现简单计算器

    • 实例代码:
    
    public class CalculatorApp {
        /** 将一个逆波兰表达式, 按各数值与运算符依次放入到 ArrayList中*/
        public static List<String> getListString(String expression) {
            String[] arr = expression.split(" ");
            List<String> list = new ArrayList<>(arr.length);
            for(String e: arr) {
                list.add(e);
            }
            return list;
        }
    
        /**
         * 逆波兰表达式的运算方法:
         * 1. 从左往右扫描表达式, 将数字3,4压入栈中
         * 2. 读到运算符+时弹出两个数(3和4), 运算后, 再将结果7压入栈内
         * 3. 再下一个数字5压入栈内
         * 4. 再读到运算符*时弹出两个数(7*5), 运算后, 再将结果35压入栈内
         * 5. 再继续将下一个数字6压入栈内
         * 6. 再读到运算符-时弹出两个数(35-6), 运算后, 再将结果29压入栈内, 即完成运算
         * */
        public static int cal(List<String> expressionList) {
            Stack<String> stack = new Stack<>();
            for (String exp : expressionList) {
                /** 是否为数值*/
                if (exp.matches("\\d+")) {
                    /** 数值直接入栈*/
                    stack.push(exp);
                } else {
                    /** 弹出两个数, 并运算*/
                    int num1 = Integer.parseInt(stack.pop());
                    int num2 = Integer.parseInt(stack.pop());
                    int res = 0;
                    if (exp.equals("+")) {
                        res = num1 + num2;
                    } else if (exp.equals("-")) {
                        res = num2 - num1;
                    } else if (exp.equals("*")) {
                        res = num1 * num2;
                    } else if (exp.equals("/")) {
                        res = num2 / num1;
                    } else {
                        throw new RuntimeException("运算符错误!");
                    }
                    /** 每次运算结果压入栈*/
                    stack.push(String.valueOf(res));
                }
            }
            /** 最后留在栈中的数值为运算结果*/
            return Integer.parseInt(stack.pop());
        }
    
        public static void main(String[] args) {
            /**
             * 中缀表达式 (3+4)*5-6的后缀表达式为  34+5*6-
             * */
            String expression = "3 4 + 5 * 6 -";
            List<String> expressionList = getListString(expression);
            int res = cal(expressionList);
            System.out.println("34+5*6-的结算结构为 " + res);
        }
    
    }
    
    输出:
    > 34+5*6-的结算结构为 29
    
    

    中缀表达式转换后缀表达式(Infix expression invert to Reverse Polish expression)

    1. 初始化两个栈: 运算符栈 s1和存储中间结果的 List s2
    2. 从左到右扫描中缀表达式
    3. 遇到操作数时, 将其直接加到 s2
    4. 遇到运算符时, 将其与 s1栈顶运算符比较优先级:
      (1) 如果 s1为空或栈顶运算符为左括号"(", 则直接将此运算符入栈
      (2) 否则, 若优先级比栈顶的运算符高, 也将运算符压入 s1
      (3) 否则, 将 s1栈顶的运算符弹出, 并压入到 s2中, 再次转到(4-1)与 s1中新的栈顶运算符相比较
    5. 遇到括号时:
      (1) 如果是左括号"(", 则直接压入 s1
      (2) 如果是右括号")", 则依次弹出 s2栈顶的运算符, 并压入 s2, 直到遇到左括号为止, 再将这一对括号丢弃
    6. 重复步骤2至5, 直到表达式的最右边
    7. 将 s1中剩余的运算符依次弹出并压入 s2
    8. 输出 s2
    • 实例代码:
    
    public class InfixToReversePolishApp {
        /** 运算符的优先级*/
        public static int operPriority(String oper) {
            if (oper.equals("*") || oper.equals("/")) {
                return 2;
            } else if(oper.equals("+") || oper.equals("-")) {
                return 1;
            } else {
                if (!oper.equals("(") && !oper.equals(")")) {
                    /** 无效的表达式*/
                    System.out.println("不存在该运算符" + oper);
                }
                return 0;
            }
        }
    
        /** 中缀表达式对应的 String List*/
        public static List<String> toInfixStringList(String infixExpression) {
            List<String> list = new ArrayList<>();
            /** 遍历中缀表达式字符串的索引*/
            int index = 0;
            /** 计算多位数时, 用于拼接的字符串变量*/
            String keepnum;
            /** 每次循环获取到的字符*/
            char ch;
            while (index < infixExpression.length()) {
                /**
                 * 不是数字, 就直接加到 List
                 * */
                if ((ch = infixExpression.charAt(index)) < 48 ||  (ch = infixExpression.charAt(index)) > 57) {
                    list.add(String.valueOf(ch));
                    index++;
                } else {
                    /** 初始化多位数拼接变量*/
                    keepnum = "";
                    /**
                     * - 不可以为最后数(由于内部循环拼接, 需要做此判断)
                     * - 每个字符必须为数字 ASCII: 48~57
                     * */
                    while (index < infixExpression.length() && (ch = infixExpression.charAt(index)) >= 48
                            && (ch=infixExpression.charAt(index)) <= 57) {
                        /** 循环拼接多位数*/
                        keepnum += ch;
                        index++;
                    }
                    list.add(keepnum);
                }
            }
            return list;
        }
    
        /** 中缀表达式 List转换后缀表达式(逆波兰表达式) List*/
        public static String infixToReversePolish(List<String> infixList) {
            /** 运算符栈(含括号)*/
            Stack<String> s1 = new Stack<>();
            /** 存转换后的后缀表达式, 只存无取, 直到方法结束返回. 注: 返回时需逆序输出*/
            List<String> s2 = new ArrayList<>();
            for(String exp: infixList) {
                /** 数字直接存入 s2*/
                if(exp.matches("\\d+")) {
                    s2.add(exp);
                } else if (exp.equals("(")) {
                    s1.push(exp);
                } else if (exp.equals(")")) {
                    /** 如果是右括号")", 则依次弹出 s1栈顶的运算符, 并压入 s2, 直到遇到左括号为止, 再将这一对括号丢弃*/
                    while(!s1.peek().equals("(")) {
                        s2.add(s1.pop());
                    }
                    s1.pop();
                } else {
                    /**
                     * 1. s1不为空
                     * 2. s1的栈顶运算符(如果是括号会返回0)大于等于 当前 exp(运算符)的优先级, 便将 s1栈顶弹出栈同时入栈到 s2
                     * */
                    while(s1.size() != 0 && operPriority(s1.peek()) >= operPriority(exp) ) {
                        s2.add(s1.pop());
                    }
                    /** 当前 exp(运算符)入栈到 s1*/
                    s1.push(exp);
                }
            }
    
            /** 将s1中剩余的运算符依次弹出栈, 并加到 s2*/
            while(s1.size() > 0) {
                s2.add(s1.pop());
            }
            return s2.parallelStream()
                    .collect(Collectors.joining());
        }
    
        public static void main(String[] args) {
            /**
             * - 中缀表达式 1+((2+3)*4)-5的后缀表达式为  123+4*+5–
             * */
            String infixExpression = "1+((2+3)*4)-5";
            List<String> infixList = toInfixStringList(infixExpression);
            System.out.println("中缀表达式对应的 List" + infixList);
            String reversePolish = infixToReversePolish(infixList);
            System.out.println("后缀表达式对应的 " + reversePolish);
        }
    
    }
    
    输出:
    > 中缀表达式对应的 List[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
    > 后缀表达式对应的 123+4*+5-
    
    

    如果您觉得有帮助,欢迎点赞哦 ~ 谢谢!!

    展开全文
  • 输入一个中缀表达式,编程输出其后缀表达式,要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。简单起见,假设输入的中缀表达式由+(加)、-(减)、×(乘)、/(除)四个运算符号以及左右...

    题目描述
    输入一个中缀表达式,编程输出其后缀表达式,要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见,假设输入的中缀表达式由+(加)、-(减)、×(乘)、/(除)四个运算符号以及左右圆括号和英文字母组成,其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过200个字符,且都是正确的,即没有语法错误,并且凡出现括号其内部一定有表达式,即内部至少有一个运算符号。

    输入
    只有一行,为中缀表达式

    输出
    只有一行,为转换后的后缀表达式

    样例输入

    X+A*(Y-B)-Z/F
    

    样例输出

    XAYB-*+ZF/-
    

    解题思路:
    建立两个栈,数据总栈与运算符栈,一个存储全部数据,一个作为中间过程需求存储运算符。

    • 遇到数字时,直接入栈->数据总栈
    • 遇到运算符时,操作如下:
      1、若此运算符是式子的第一个运算符或者为’(’ ,直接入栈->运算符栈。
      2、若为’)’ :出栈所有运算符,并入栈->数据总栈,直到遇到 ‘(’,最后将 '('出栈。
      3、若此运算符的优先级大于运算符栈栈顶运算符,则直接入栈->运算符栈,
      否则,运算符栈栈顶运算符出栈,随后入栈->数据总栈。此运算符接替栈顶的位置,再与前一位运算符比较,重复上述操作,直到此运算符的优先级大于前一位运算符。
    • 当数据都操作完后,出栈所有运算符栈的运算符,依次入栈->数据总栈。

    代码如下:

    #include <stdio.h>
    
    /*符号栈*/
    struct Symbol
    {
    	int top;
    	char s[400];
    }symbol;
    
    /*数据总栈*/
    struct Number
    {
    	int top;
    	char n[400];
    }number;
    
    //栈的初始化
    void init()
    {
    	symbol.top = -1;
    	number.top = -1;
    }
    
    //将运算符替换成数字以比较优先级
    /*优先级:【'*'='/'】 > 【'+'='-'】 > 【'('】 */ 
    int replace(char a)
    {
    	switch (a)
    	{
    		case '+':return 1;
    		case '-':return 1;
    		case '*':return 2;
    		case '/':return 2;
    		case '(':return 0;
    	}
    }
    
    //优先级的比较
    /* s为符号栈的栈顶运算符,e为待定运算符
    	若s<e,则返回1,后续操作为直接将e添加到符号栈栈顶
    	否则,返回0,后续操作为将符号栈栈顶运算符出栈,并添加到数据总栈,
    	再将e添加到符号栈栈顶*/
    int compare(char s, char e)
    {
    	return (replace(s) < replace(e)) ? 1 : 0;
    }
    
    //后缀表达式转换
    void reversePolish(char ex[])
    {
    	for (int i = 0; ex[i] != '\0'; i++)
    	{
    		/*若字符为A-Z,直接添加到数据总栈*/
    		if (ex[i] <= 'Z' && ex[i] >= 'A' || ex[i] <= 'z' && ex[i] >= 'a')
    		{
    			number.n[++number.top] = ex[i];
    		}
    
    		else
    		{
    			if (symbol.top == -1) { symbol.s[++symbol.top] = ex[i]; continue; }
    			if (ex[i] == '(') { symbol.s[++symbol.top] = ex[i]; continue; }
    			/*若ex[i]为')',则将运算符栈栈顶运算符出栈 添加到数据总栈,直到运算符栈栈顶为')'*/
    			if (ex[i] == ')')
    			{
    				while (symbol.s[symbol.top] != '(')
    				{
    					number.n[++number.top] = symbol.s[symbol.top];
    					symbol.top--;
    				}
    				symbol.top--;
    				continue;
    			}
    			
    			/*比较运算符栈顶运算符symbol.s[symbol.top],与待定运算符ex[i]的优先级*/
    			if (compare(symbol.s[symbol.top], ex[i])) symbol.s[++symbol.top] = ex[i];
    			/*若成立,直接将ex[i]添加到符号栈栈顶*/
    			/*不成立,先将运算符栈顶运算符出栈,添加到数据总栈,
    			然后将ex[i]入运算符栈,再与前一位运算符比较,循环上述操作,
    			直到运算符栈顶运算符优先级大于它的前一位运算符*/
    			else
    			{
    				number.n[++number.top] = symbol.s[symbol.top];
    				symbol.s[symbol.top] = ex[i];
    				while (!compare(symbol.s[symbol.top - 1], symbol.s[symbol.top]) && symbol.top > 0)
    				{
    					number.n[++number.top] = symbol.s[symbol.top - 1];
    					symbol.s[symbol.top - 1] = symbol.s[symbol.top];
    					symbol.top--;
    				}
    			}
    		}
    	}
    	/*将运算符栈剩余的运算符依次出栈并添加到数据总栈*/
    	while (symbol.top != -1)
    	{
    		number.n[++number.top] = symbol.s[symbol.top];
    		symbol.top--;
    	}
    }
    
    //输出结果(后缀表达式)
    void printList()
    {
    	for (int i = 0; i <= number.top; i++)
    	{
    		printf("%c", number.n[i]);
    	}
    }
    
    int main() {
    	char ex[400];
    	init();
    	scanf("%s", ex);
    	reversePolish(ex);
    	printList();
    
    	return 0;
    }
    
    展开全文
  • 将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要省略,不影响原计算顺序的括号要...
  • 思路是这样的,后缀表达式不用管计算顺序,但是有一点是在必要的时候添加括号,我是建了一个结构,包含一个表达式和这个表达式最外层的运算符。结合的时候注意比较优先级进而添加括号。 #include #include #...
  • 请设计程序将中缀表达式转换为后缀表达式。 输入格式: 输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。 输出格式: 在一行中输出转换后的后缀表达式,要求不同对象...
  • 一、算术表达式 ... 采用树的数据结构,缺点是如果表达式过于复杂,树的高度会很高,极大的增加了时间复杂度和空间复杂度,但是转换成线性结构,效率将会提高很多,所以需要将中缀表达式转换成前缀或...
  • 中缀表达式后缀表达式的转换规则 前面我们提到计算机易于理解前缀表达式和后缀表达式,但我们生活中或使用计算器时是中缀表达式,这也就意味着我们需要将中缀表达式转换为前缀或后缀表达式,从而实现计算器的高效...
  • 表达式的转换中缀表达式转化为后缀表达式 C语言编程
  • 栈的应用——表达式求解,内容主要有 中缀表达式转换后缀表达式以及求解过程,需要可自行下载
  • 该程序实现了运算表达式转换为中缀表达式、中缀表达式转换为后缀表达式后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
  • 表达式树—中缀表达式转换后缀表达式(一) 前缀、中缀、后缀表达式的转换举例 前缀表达式:/+A*BCD。 中缀表达式:A+B*C/D。 后缀表达式:ABC*+D/。 中缀表达式转换后缀表达式算法 将...
  • 后缀表达式的处理过程如下:扫描后缀表达式,凡遇操作数则将之压进堆栈,遇运算符则从堆栈中弹出两个操作数进行该运算,将运算结果压栈,然后继续扫描,直到后缀表达式被扫描完毕为止,此时栈底元素即该后
  • 中缀表达式后缀表达式
  • 逆波兰表达式,也叫做后缀表达式。如图: 我们平时见到的运算表达式是中缀表达式,即 “操作数① 运算符② 操作数③” 的顺序,运算符在两个操作数中间。 但是后缀表达式是 “操作数① 操作数③ 运算符②” 的顺序...
  • 中缀表达式转换为后缀表达式

    万次阅读 多人点赞 2017-04-22 11:50:10
    假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下: 1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示: 2)接着读到“+”,则弹出3和2,执行3+2,计算结果等于5,并将5压入到栈中。 ...
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • 考研中有一类经典的问题就是表达式的转换问题,经常要把一个类型的表达式转换为另一个类型的表达式 所以这里我们主要说一下中缀转前缀,前缀转中缀中缀后缀后缀中缀即可。这样这三种形式任意两个之间的转换...
  • 中缀表达式的计算: #include #include #include #define maxsize 100 //栈操作的应用 //author:Hacker Li //time:2015.5.21 //转载请注明出处:http://blog.csdn.net/xdz78 int hash[50]; char p[100]; char b...
  • 主要大家详细介绍了C语言实现中缀表达式转换为后缀表达式,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,429
精华内容 3,771
关键字:

后缀表达式转换为中缀表达式