精华内容
下载资源
问答
  • 前缀表达式

    2013-04-18 16:48:06
    前缀表达式就是前序表达式 前缀表达式就是前序表达式。 编辑本段什么是前缀表达式 前缀表达式就是不含括号的算术...编辑本段前缀表达式如何求值 对于一个前缀表达式的求值而言,首先要从右至左扫描表达式,从右

    前缀表达式就是前序表达式

    前缀表达式就是前序表达式

    编辑本段什么是前缀表达式

    前缀表达式就是不含括号的算术表达式,而且它是将运算符写在前面,操作数写在后面的表达式,为纪念其发明者波兰数学家Jan Lukasiewicz也称为“波兰式”。例如,- 1 + 2 3,它等价于1-(2+3)。

    编辑本段前缀表达式如何求值

    对于一个前缀表达式的求值而言,首先要从右至左扫描表达式,从右边第一个字符开始判断,如果当前字符是数字则一直到数字串的末尾再记录下来,如果是运算符,则将右边离得最近的两个“数字串”作相应的运算,以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时,最后运算的值也就是表达式的值。例如,前缀表达式“- 1 + 2 3“的求值,扫描到3时,记录下这个数字串,扫描到2时,记录下这个数字串,当扫描到+时,将+右移做相邻两数字串的运算符,记为2+3,结果为5,记录下这个新数字串,并继续向左扫描,扫描到1时,记录下这个数字串,扫描到-时,将-右移做相邻两数字串的运算符,记为1-5,结果为-4,所以表达式的值为-4。

    编辑本段前缀表达式有什么用处

    前缀表达式是一种十分有用的表达式,它将中缀表达式转换为可以依靠简单的操作就能得到运算结果的表达式。例如,(a+b)*(c+d)转换为*,+,a,b,+,c,d。它的优势在于只用两种简单的操作,入栈和出栈就可以解决任何中缀表达式的运算。其运算方式为:如果当前字符(或字符串)为数字或变量,则压入栈内;如果是运算符,则将栈顶两个元素弹出栈外并作相应运算,再将结果压入栈内。当前缀表达式扫描结束时,栈里的就是中缀表达式运算的最终结果。

    编辑本段中缀表达式转换为前缀表达式的一些例子

    a+b ---> +,a,b 
    a+(b-c) ---> +,a,-,b,c 
    a+(b-c)*d ---> +,a,*,-,b,c,d 
    a=1+3 ---> =,a,+,1,3

    编辑本段中缀表达式转换为前缀表达式的一般算法

    (1) 首先构造一个运算符栈(也可放置括号),运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。 
    (2)从右至左扫描中缀表达式,从右边第一个字符开始判断: 
    如果当前字符是数字,则分析到数字串的结尾并将数字串直接输出。 
    如果是运算符,则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),则将运算符直接入栈;否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),再将当前运算符入栈。 
    如果是括号,则根据括号的方向进行处理。如果是右括号,则直接入栈;否则,遇左括号前将所有的运算符全部出栈并输出,遇左括号后将左右的两括号一起删除。 
    (3) 重复上述操作(2)直至扫描结束,将栈内剩余运算符全部出栈并输出,再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

    编辑本段实例分析

    将中缀表达式“1+((2+3)*4)-5”转换为前缀表达式。 
    中缀表达式
    前缀表达式
    (栈顶)运算符栈(栈尾)
    说明 
    5
    5
    5,是数字串直接输出
    -
    5
    -
    -,栈内无运算符,直接入栈
    5
    -)
    ),直接入栈
    4
    5 4
    -)
    4,是数字串直接输出
    *
    5 4
    -)*
    *,栈顶是括号,直接入栈
    )
    5 4
    - ) * )
    ),直接入栈 
    3
    5 4 3
    - ) * )
    3,是数字串直接输出
    +
    5 4 3
    - ) * ) +
    +,栈顶是括号,直接入栈
    2
    5 4 3 2
    - ) * )+
    2,是数字串直接输出
    (
    5 4 3 2+
    - ) *
    (,参考① 
    (
    5 4 3 2+*
    -
    (,参考①
    +
    5 4 3 2+*
    -+
    +,优先级大于等于栈顶运算符,直接入栈
    1
    5 4 3 2+*1
    -+
    1,是数字串直接输出
    5 4 3 2+*1+-
    扫描结束,将栈内剩余运算符全部出栈并输出
    - + 1 * + 2 3 4 5
    逆缀输出字符串

    编辑本段各运算符及符号优先级

    ):直接入栈 
    (:遇)前,将运算符全部出栈并输出;遇)后,将两括号一起删除①
    +、-:1 
    *、/、%:2 
    ^:3

    编辑本段用编程实现中缀表达式向前缀表达式的转换

    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    #include<string.h>
    #define MaxSize 99
    char calc[MaxSize],expr[MaxSize];
    int i,t;
    struct
    {
    char data[MaxSize];
    int top;
    }Sym;
    struct
    {
    double data[MaxSize];
    int top;
    }Num;
    double ston(char x[],int *p)
    {
    int j=*p-1,i;
    double n=0,m=0;
    while(x[j]>='0'&&x[j]<='9')
    {
    j--;
    }
    if(x[j]!='.')
    {
    for(i=j+1;i<=*p;i++)
    {
    n=10*n+(x[i]-'0');
    }
    }
    else
    {
    for(i=j+1;i<=*p;i++)
    {
    m=m+pow(0.1,i-j)*(x[i]-'0');
    }
    if(x[j]=='.')
    {
    *p=--j;
    while(x[j]>='0'&&x[j]<='9')
    {
    j--;
    }
    for(i=j+1;i<=*p;i++)
    {
    n=10*n+(x[i]-'0');
    }
    }
    }
    *p=j;
    if(x[*p]=='-') return(-(n+m));
    return(n+m);
    }
    void InitStack()
    {
    Sym.top=Num.top=-1;
    }
    void SymPush()
    {
    if(Sym.top<MaxSize-1)
    {
    Sym.data[++Sym.top]=calc[i--];
    }
    else
    {
    printf("Sym栈满\n");
    return;
    }
    }
    void SymPop()
    {
    if(Sym.top>=0)
    {
    expr[++t]=Sym.data[Sym.top--];
    }
    else
    {
    printf("Sym栈空\n");
    return;
    }
    }
    void NumPush()
    {
    if(Num.top<MaxSize-1)
    {
    Num.data[++Num.top]=ston(expr,&i);
    }
    else
    {
    printf("Num栈满\n");
    return;
    }
    }
    void NumPop()
    {
    if(Num.top>=0)
    {
    if(expr[i]!=' ')
    {
    switch(expr[i])
    {
    case '+':Num.data[Num.top-1]=Num.data[Num.top]+Num.data[Num.top-1];break;
    case '-':Num.data[Num.top-1]=Num.data[Num.top]-Num.data[Num.top-1];break;
    case '*':Num.data[Num.top-1]=Num.data[Num.top]*Num.data[Num.top-1];break;
    case '/':Num.data[Num.top-1]=Num.data[Num.top]/Num.data[Num.top-1];break;
    case '^':Num.data[Num.top-1]=pow(Num.data[Num.top],Num.data[Num.top-1]);break;
    }
    Num.top--;
    }
    }
    else
    {
    printf("Num栈空\n");
    return;
    }
    }
    int main(void)
    {
    char ch;
    loop1:
    i=0,t=-1;
    system("cls");
    printf("中缀表达式:");
    InitStack(),gets(calc);
    while(calc[i]!='\0')
    {
    i++;
    }
    while(i>=0)
    {
    if(calc[i]>='0'&&calc[i]<='9')
    {
    while((i>=0)&&((calc[i]>='0'&&calc[i]<='9')||(calc[i]=='.')))
    {
    loop2:
    expr[++t]=calc[i--];
    }
    if((i>=0)&&((i==0&&calc[i]!='(')||(calc[i]=='+'||calc[i]=='-')&&!(calc[i-1]>='0'&&calc[i-1]<='9')&&calc[i-1]!=')')) goto loop2;
    expr[++t]=' ';
    }
    else if(calc[i]==')')
    {
    SymPush();
    }
    else if(calc[i]=='(')
    {
    while(Sym.data[Sym.top]!=')')
    {
    SymPop();
    expr[++t]=' ';
    }
    Sym.data[Sym.top--]='\0';
    i--;
    }
    else if(calc[i]=='+'||calc[i]=='-')
    {
    while(Sym.top>=0&&Sym.data[Sym.top]!=')'&&Sym.data[Sym.top]!='+'&&Sym.data[Sym.top]!='-')
    {
    SymPop();
    expr[++t]=' ';
    }
    SymPush();
    }
    else if(calc[i]=='*'||calc[i]=='/')
    {
    while(Sym.top>=0&&Sym.data[Sym.top]=='^')
    {
    SymPop();
    expr[++t]=' ';
    }
    SymPush();
    }
    else if(calc[i]=='^')
    {
    SymPush();
    }
    else
    {
    i--;
    }
    }
    while(Sym.top>=0)
    {
    SymPop();
    expr[++t]=' ';
    }
    expr[++t]=Sym.data[++Sym.top]='\0';
    for(i=0;i<=(t-2)/2;i++)
    {
    ch=expr[i];
    expr[i]=expr[(t-2)-i];
    expr[(t-2)-i]=ch;
    }
    printf("前缀表达式:%s\n",expr);
    for(i=t-2;i>=0;i--)
    {
    if((expr[i]>='0'&&expr[i]<='9')||((expr[i]=='+'||expr[i]=='-')&&(expr[i+1]>='0'&&expr[i+1]<='9')))
    {
    NumPush();
    }
    else
    {
    NumPop();
    }
    }
    printf("运算结果为:%g\n",Num.data[0]);
    printf("Continue(y/n)?");
    ch=getch();
    switch(ch)
    {
    case 'y':{system("cls");goto loop1;}
    case 'n':
    default :exit(0);
    }
    getch();
    return(0);
    }

    编辑本段后缀表达式转前缀表达式

    var
    a:array[1..1000] of string;
    s:string;
    i,j,k,l,v:longint;
    begin
    readln(s);
    j:=0; l:=length(s);
    for i:=1 to l do
    begin
    if not(s[i]in['+','-','*','/']) then
    begin
    j:=j+1;
    a[j]:=s[i];
    end
    else
    begin
    if (j>1)and(s[i]in['/'])and(s[i-1]in['*','/']) then
    a[j]:='('+a[j]+')';
    j:=j-1;
    a[j]:=a[j]+s[i]+a[j+1];
    if (i<l)and(s[i]in['+','-']) then
    begin
    k:=i;
    v:=0;
    repeat
    k:=k+1;
    if s[k]in['+','-','*','/'] then v:=v-1
    else v:=v+1;
    until (k=l)or(v<1);
    if (k<l)and(s[k]in['*','/']) then a[j]:='('+a[j]+')';
    end;
    end;
    end;
    writeln(a[1]);
    end.


    展开全文
  • 如何根据前缀表达式运算出对应的值 例如 1 + (2 + 3) × 4 - 5 如何将该中缀表达式转换成前缀表达式 我们只需给每一层计算按对应的优先级加上括号 上式则为 ((1+((2+3)×4)))-5) 前缀表达即是将符号拿在...

    前缀表达式

    如何根据前缀表达式运算出对应的值
    例如 1 + (2 + 3) × 4 - 5
    如何将该中缀表达式转换成前缀表达式
    我们只需给每一层计算按对应的优先级加上括号
    上式则为
    ((1+((2+3)×4)))-5)
    前缀表达即是将符号拿在括号的前面
    -(+(1×(+(23)4))5)
    那怎么将前缀表达式还原成中缀呢
    我们从右到左开始读前缀表达式
    这时候我们会遇见两种情况
    1.当遇到数字则放入栈中
    2.当遇见运算符则把栈中的数字push两个出来并进行运算后放回栈中

    这样最终就会算出结果

    后缀表达式

    同样后缀也是按对应的优先级加上括号,但是我们将符号放在括号后
    ((1((23)+4)×)+5)-
    那怎么将后缀表达式还原成中缀呢
    则从左往右读后缀表达式
    这时候我们会遇见两种情况
    1.当遇到数字则放入栈中
    2.当遇见运算符则把栈中的数字push两个出来并进行运算后放回栈中

    这样最终就会算出结果

    展开全文
  • 如何将中缀表达式(3+4)*5-6转换成前缀表达式 - * + 3 4 5 6。 将中缀表达式转换为前缀表达式: 遵循以下步骤: 初始化两个栈:运算符栈S1和储存中间结果的栈S2; 从右至左扫描中缀表达式; 遇到操作数时,将其压...

    前缀表达式

    前缀表达式又称波兰式,前缀表达式的运算符位于操作符之前。
    例:(3+4)*5-6对应的前缀表达式就是 - * + 3 4 5 6
    如何将中缀表达式(3+4)*5-6转换成前缀表达式 - * + 3 4 5 6。

    • 将中缀表达式转换为前缀表达式:

    遵循以下步骤:

    1. 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
    2. 从右至左扫描中缀表达式;
    3. 遇到操作数时,将其压入S2;
    4. 遇到运算符时,比较其与S1栈顶运算符的优先级:
      如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈;
      若优先级比栈顶运算符的较高或相等,也将运算符压入S1;
      否则,将S1栈顶的运算符弹出并压入到S2中,再次转到与S1中新的栈顶运算符相比较;
    5. 遇到括号时:
      如果是右括号“)”,则直接压入S1;
      如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃;
    6. 重复步骤(2)至(5),直到表达式的最左边;
    7. 将S1中剩余的运算符依次弹出并压入S2;
    8. 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。

    因此中缀表达式(3+4)*5-6转换成前缀表达式 的结果是 - * + 3 4 5 6。

    • 前缀表达式求值
      右至左扫描表达式,遇到数字时将数字压入栈,遇到运算符,弹出栈顶的2个数,用运算符做出计算,并把计算的结果入栈;重复上述过程,直到表达式的左端,最后运算得出的值即为表达式的结果。

    • 代码实现

    public class PrefixExpression {
    
        public static void main(String[] args) {
            String expression = "(3 + 4) * 5 - 6";
            String prefixExpression = getPrefixExpression(expression);
    
            System.out.println("prefixExpression = " + prefixExpression);
    
            int expressionValue = getPrefixExpressionValue(prefixExpression);
            System.out.println( expression +" = " + expressionValue);
    
        }
    
        /**
        	求值
         *      - * + 3 4 5 6
         * 从右至左扫描表达式,遇到数字时将数字压入栈,
         * 遇到运算符,弹出栈顶的2个数,用运算符做出计算,并把计算的结果入栈;
         * 重复上述过程,直到表达式的左端,最后运算得出的值即为表达式的结果。
         * @param prefixExpression
         * @return
         */
        public static int getPrefixExpressionValue(String prefixExpression) {
            // 1.把表达式转成list集合
            List<String> prefixExpressionList = getList(prefixExpression);
            Stack<String> stack = new Stack<>();
    
            for (int i = prefixExpressionList.size() - 1; i >= 0; i--) {
                String value = prefixExpressionList.get(i);
                if (isNumber(value)) {
                    stack.push(value);
                }
                if (is0perator(value)) {
                    int num1 = Integer.parseInt(stack.pop());
                    int num2 = Integer.parseInt(stack.pop());
                    if ("+".equals(value)) {
                        int n = num1 + num2;
                        stack.push(Integer.toString(n));
                    }else if ("-".equals(value)){
                        int n = num1 - num2;
                        stack.push(Integer.toString(n));
                    }else if ("*".equals(value)) {
                        int n = num1 * num2;
                        stack.push(Integer.toString(n));
                    }else if ("/".equals(value)) {
                        int n = num1 / num2;
                        stack.push(Integer.toString(n));
                    }
                }
    
            }
    
            int value = Integer.parseInt(stack.pop());
            return value;
        }
    
    
        /**
         * (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
         * (2) 从右至左扫描中缀表达式;
         * (3) 遇到操作数时,将其压入S2;
         * (4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
         * (4-1) 如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈;
         * (4-2) 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1;
         * (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
         * (5) 遇到括号时:
         * (5-1) 如果是右括号“)”,则直接压入S1;
         * (5-2) 如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃;
         * (6) 重复步骤(2)至(5),直到表达式的最左边;
         * (7) 将S1中剩余的运算符依次弹出并压入S2;
         * (8) 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。
         * @param expression
         * @return
         */
        private static String getPrefixExpression(String expression) {
            // "(3 + 4) * 5 - 6";
            if (expression == null || expression == "") {
                return null;
            }
    
            // 初始化一个栈和一个集合
            Stack<String> s1 = new Stack<>();
            List<String> s2 = new ArrayList<>();
    
            List<String> expressionList = getList(expression);
            // 从右至左扫描表达式即从集合的末尾往前遍历
            for (int i = expressionList.size()-1; i >= 0; i--) {
                String s = expressionList.get(i);
                // 是数字
                 if (isNumber(s)) {
                    s2.add(s);
                 }
    
                 // 是运算符
                 if (is0perator(s)) {
                     while (true) {
                         if (s1.empty() || ")".equals(s1.peek())) {
                             s1.push(s);
                             break;
                         } else if (is0perator(s1.peek())) {
                             if (isPriority(s, s1.peek())) {
                                 s1.push(s);
                                 break;
                             }else {
                                 s2.add(s1.pop());
                             }
                         }
                     }
                 }
    
                 // 是括号
                 if ("(".equals(s) || ")".equals(s)) {
                    if (")".equals(s)) {
                        s1.push(s);
                    }
                    if ("(".equals(s)) {
                        while (true) {
                            String pop = s1.pop();
                            if (")".equals(pop)) {
                                break;
                            }
                            s2.add(pop);
                        }
                    }
                 }
    
            }
    
            // 将S1中剩余的运算符依次弹出并压入S2;
            while (!s1.empty()) {
                s2.add(s1.pop());
            }
    
            // S2中的元素逆序,结果即为中缀表达式对应的前缀表达式。
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = s2.size() - 1; i >= 0; i--) {
                stringBuilder.append(" "+s2.get(i));
            }
    
            return stringBuilder.toString();
        }
    
        private static boolean isPriority(String operator1, String operator2) {
            if ("+".equals(operator1) || "-".equals(operator1)) {
                if ("+".equals(operator2) || "-".equals(operator2)) {
                    return true;
                }
                if ("*".equals(operator2) || "/".equals(operator2)) {
                    return false;
                }
            }
            if ("*".equals(operator1) || "/".equals(operator1)) {
                return true;
            }
            return false;
        }
    
        private static boolean isNumber(String str){
            String reg = "^[0-9]+(.[0-9]+)?$";
            return str.matches(reg);
        }
    
        private static boolean is0perator(String str) {
            if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {
                return true;
            }
            return false;
        }
    
        /**
         * 把字符串转成集合
         * @param expression
         * @return
         */
        private static List<String> getList(String expression) {
            List<String> list = new ArrayList<>();
    
            char[] charArray = expression.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                String s = Character.toString(charArray[i]);
                // 判断字符是不是数字
                if (isNumber(s)) {
                    // 在判断他的下一个字符还是不是数字
                    while (i < charArray.length - 1) {
                        String nextS = Character.toString(charArray[i + 1]);
                        if (isNumber(nextS)) {
                            s += nextS;
                            i++;
                        } else {
                            break;
                        }
                    }
                }
    
                if (!" ".equals(s)) {
                    list.add(s);
                }
            }
    
    
          return list;
        }
    }
    

    运行结果:

    prefixExpression =  - * + 3 4 5 6
    (3 + 4) * 5 - 6 = 29
    

    后缀表达式

    • 将中缀表达式转换为后缀表达式
    1. 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
    2. 从左至右扫描中缀表达式;
    3. 遇到操作数时,将其压入S2;
    4. 遇到运算符时,比较其与S1栈顶运算符的优先级:
      如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
      否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
      否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
    5. 遇到括号时:
      如果是左括号“(”,则直接压入S1;
      如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
    6. 重复步骤(2)至(5),直到表达式的最右边;
    7. 将S1中剩余的运算符依次弹出并压入S2;
    8. 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。

    例如,将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的结果就是:1 2 3 + 4 × + 5 -

    • 后缀表达式的计算机求值
      与前缀表达式类似,只是顺序是从左至右:
      从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
      例如后缀表达式“3 4 + 5 × 6 -”:
      (1) 从左至右扫描,将3和4压入堆栈;
      (2) 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈;
      (3) 将5入栈;
      (4) 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
      (5) 将6入栈;
      (6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。
    public class SuffixExpression {
    
        public static void main(String[] args) {
            String expression = "1+((2+3)*4)-5";
            String suffixExpression = getSuffixExpression(expression);
            System.out.println("suffixExpression = " + suffixExpression);
    
            int expressionValue = getSuffixExpressionValue(suffixExpression);
            System.out.println("expressionValue = " + expressionValue);
    
        }
    
    
        /**
        * (1. 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
         * 2. 从**左至右扫**描中缀表达式;
         * 3. 遇到操作数时,将其压入S2;
         * 4. 遇到运算符时,比较其与S1栈顶运算符的优先级:
         *     如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
         *     否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
         *    否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
         * 5. 遇到括号时:
         *     如果是左括号“(”,则直接压入S1;
         *     如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
         * 6. 重复步骤(2)至(5),直到表达式的最右边;
         * 7. 将S1中剩余的运算符依次弹出并压入S2;
         * 8. 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。
        * @param expression
         * @return
                 */
        private static String getSuffixExpression(String expression) {
            // "1+((2+3)×4)-5";
            if (expression == null || expression == "") {
                return null;
            }
    
            // 初始化一个栈和一个集合
            Stack<String> s1 = new Stack<>();
            List<String> s2 = new ArrayList<>();
    
            List<String> expressionList = getList(expression);
            // 从左至右扫描表达式即从集合的末尾往前遍历
            for (int i = 0; i < expressionList.size(); i++) {
                String s = expressionList.get(i);
                // 是数字
                if (isNumber(s)) {
                    s2.add(s);
                }
    
                // 是运算符
                if (is0perator(s)) {
                    while (true) {
                        if (s1.empty() || "(".equals(s1.peek())) {
                            s1.push(s);
                            break;
                        } else if (is0perator(s1.peek())) {
                            if (isPriority(s, s1.peek())) {
                                s1.push(s);
                                break;
                            }else {
                                s2.add(s1.pop());
                            }
                        }
                    }
                }
    
                // 是括号
                if ("(".equals(s) || ")".equals(s)) {
                    if ("(".equals(s)) {
                        s1.push(s);
                    }
                    if (")".equals(s)) {
                        while (true) {
                            String pop = s1.pop();
                            if ("(".equals(pop)) {
                                break;
                            }
                            s2.add(pop);
                        }
                    }
                }
    
            }
    
            // 将S1中剩余的运算符依次弹出并压入S2;
            while (!s1.empty()) {
                s2.add(s1.pop());
            }
    
            // S2中的元素逆序,结果即为中缀表达式对应的前缀表达式。
            StringBuilder stringBuilder = new StringBuilder();
            for (String s : s2) {
                stringBuilder.append(" "+ s);
            }
    
            return stringBuilder.toString();
        }
    
    
        /**
         *   与前缀表达式类似,只是顺序是从左至右:
         * 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,
         * 用运算符对它们做相应的计算(次顶元素 op 栈顶元素),
         * 并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
         *
         * 例如后缀表达式“3 4 + 5 × 6 -”:
         * (1) 从左至右扫描,将3和4压入堆栈;
         * (2) 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈;
         * (3) 将5入栈;
         * (4) 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
         * (5) 将6入栈;
         * (6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。
         * @param suffixExpression
         * @return
         */
        public static int getSuffixExpressionValue(String suffixExpression) {
            // 1.把表达式转成list集合
            List<String> suffixExpressionExpressionList = getList(suffixExpression);
            Stack<String> stack = new Stack<>();
    
            for (int i = 0; i < suffixExpressionExpressionList.size(); i++) {
                String value = suffixExpressionExpressionList.get(i);
                if (isNumber(value)) {
                    stack.push(value);
                }
                if (is0perator(value)) {
                    int num1 = Integer.parseInt(stack.pop());
                    int num2 = Integer.parseInt(stack.pop());
                    if ("+".equals(value)) {
                        int n = num2 + num1;
                        stack.push(Integer.toString(n));
                    }else if ("-".equals(value)){
                        int n = num2 - num1;
                        stack.push(Integer.toString(n));
                    }else if ("*".equals(value)) {
                        int n = num2 * num1;
                        stack.push(Integer.toString(n));
                    }else if ("/".equals(value)) {
                        int n = num2 / num1;
                        stack.push(Integer.toString(n));
                    }
                }
    
            }
    
            int value = Integer.parseInt(stack.pop());
            return value;
        }
    
        private static boolean isPriority(String operator1, String operator2) {
            if ("+".equals(operator1) || "-".equals(operator1)) {
                return false;
    
            }
            if ("*".equals(operator1) || "/".equals(operator1)) {
    
                if ("+".equals(operator2) || "-".equals(operator2)) {
                    return true;
                }
                if ("*".equals(operator2) || "/".equals(operator2)) {
                    return false;
                }
            }
            return false;
        }
    
        private static boolean isNumber(String str){
            String reg = "^[0-9]+(.[0-9]+)?$";
            return str.matches(reg);
        }
    
        private static boolean is0perator(String str) {
            if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {
                return true;
            }
            return false;
        }
    
        /**
         * 把字符串转成集合
         * @param expression
         * @return
         */
        private static List<String> getList(String expression) {
            List<String> list = new ArrayList<>();
    
            char[] charArray = expression.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                String s = Character.toString(charArray[i]);
                // 判断字符是不是数字
                if (isNumber(s)) {
                    // 在判断他的下一个字符还是不是数字
                    while (i < charArray.length - 1) {
                        String nextS = Character.toString(charArray[i + 1]);
                        if (isNumber(nextS)) {
                            s += nextS;
                            i++;
                        } else {
                            break;
                        }
                    }
                }
    
                if (!" ".equals(s)) {
                    list.add(s);
                }
            }
    
            return list;
        }
    }
    

    运算结果是:

    suffixExpression =  1 2 3 + 4 * + 5 -
    expressionValue = 16
    
    展开全文
  • 关于前缀表达式

    2018-11-26 19:46:26
    前缀表达式 例如((34+22) - (24/11) * 12) * 3.5 / (23 * 12/11) 写成前缀表达式就是 / * - + 34 22 * / 24 11 12 3.5 * 23 / 12 11 前缀表达式的运算法则就是如果读取的是一个运算符号,就向下寻找两个数据进行运算...

    前缀表达式

    例如((34+22) - (24/11) * 12) * 3.5 / (23 * 12/11)
    写成前缀表达式就是 / * - + 34 22 * / 24 11 12 3.5 * 23 / 12 11
    前缀表达式的运算法则就是如果读取的是一个运算符号,就向下寻找两个数据进行运算。

    递归的思想

    如何读取数据和字符

    其实不用开很多字符数组。
    用cin读取字符就可以了,进而在递归函数里面来处理这个字符。
    可以开一个短一点的字符数组来储存数据或者运算符号然后传递给函数即可。

    递归函数如何处理传递进来的数据或者运算符号

    秉承一个思路:如果是运算符号就向下寻找两个数据,然后用相应的运算符号来激素那结果并且返回给上一个函数;如果是数字,就转换成浮点数返回给上一个函数。

    实现方法

    double solve()
    {
    	cin >> digit_or_num;
    	if (digit_or_num[0] == '+')
    		return solve() + solve();
    	if (digit_or_num[0] == '-')
    		return solve() - solve();
    	if (digit_or_num[0] == '*')
    		return solve() * solve();
    	if (digit_or_num[0] == '/')
    		return solve() / solve();
    	else
    		return atof(digit_or_num);//将字符串转化为浮点数
    }
    

    我的脑回路

    思考目的:每一个函数需要什么样的参数来实现代码的目的,这个题需要每次返回一个浮点数。如果是运算符号,就要获得两个浮点数,所以调用两次函数,分别获得一个浮点数;如果是数字,就可以返回一个合法的浮点数,供上一个函数利用。

    代码

    (悄咪咪)放上来递归函数的代码应该主函数不需要了吧,主函数只需要控制输出格式就行了。

    后记

    傻fufu的博主依然不知道怎么控制代码块的颜色。

    展开全文
  • 中缀表达式就是我们数学中常用的那种表达式,本文打算以中缀表达式:1 + (2 + 3) × 4 - 5 为例,分享一下前缀表达式和后缀表达式的如何形成与在计算机如何计算前后最表达式和后缀表达式 1、前缀表达式和后缀表达式...
  • 认识前缀、中缀、后缀表达式: 一般我们平时用的计算式都是中缀表达式,因为符号都是在操作数的中间的。相对应的符号在操作数后面的就叫后缀表达式(也称逆波兰...计算机如何计算后缀,前缀表达式? 计算后缀:从左到...
  • 上一篇文章,楼主分享了自己如何将一个中缀表达式转化成后缀表达式并求值,在这篇文章当中楼主将介绍如何将一个中缀表达式转换成一个前缀表达式并求值。
  • 栈实现后缀表达式转前缀表达式

    千次阅读 2018-01-14 15:42:23
    先看下面的图片,这是后缀表达式32/6*3-3+转前缀的过程 对于表达式:32/6*3-3+ 其前缀式为:+-*/32633 操作数的顺序不会改变,变的是运算符的顺序,并且在后缀式中,运算顺序从左往...
  • 前缀表达式: 一种可以将 普通的运算式 描述成 堆栈执行顺序 的表达式(特别适合计算机或者算法的理解) 比如 : a+b ---> +,a,b  a+(b-c) --->... 5 : 6 这该如何 描述成 前缀表达式??
  • 我做的实验是一个表达式二叉树,声明Operators运算符集合类,提供运算符及其优先级,按优先级比较运算符大小的函数,两个操作数进行指定运算的函数等。 声明ExpressionBinaryTree表达式二叉树类(教材图6.11)如下,...
  • 前一篇文章讲了如何解析let与return,那么今天就讲如何parse前缀表达式. 1.前缀表达式都包含什么 变量名 数字 "!"感叹号 "-"减号 逻辑值 true,false "("左小括号 if关键字 fn关键字 字符串 "{"左大括号 "["左...
  • 【朝夕的ACM笔记】目录与索引前缀和一、什么是前缀和?一维前缀和:有一个一维数组 和该数组的一维前缀和数组 ,则 和 满足以下关系: 二维前缀和:有一个二维数组 和该数组的二...二、如何得到前缀和?一维前缀和:...
  • 笔者也深有感触,但是自从C++11标准出现以后,CPP的代码就开始精简很多了,风格也极大的发生了变化,今天笔者就开始整理一些C++的新特性,并展示如何在实际应用中使用!让你的代码更Cpp些!前缀树结构图1....
  • 相信大家肯定有注意过这样一个细节:当输入某个字符的时候,搜索引框底下会出现多个推荐词,如下,输入「python」后,底下会出现挺多以python 为前缀的推荐搜索文本,它是如何实现的呢?文章标题已经给出答案了,没错...
  • 表达式/如何将中缀表达式转化成后缀表达式

    千次阅读 多人点赞 2017-05-27 21:24:03
    表达式一般分为前缀表达式,中缀表达式和后缀表达式。其中我们最为熟悉的是中缀表达式,也就是书本上最常用的表示形式。中缀表达式是将运算符放在两个操作数的中间。 前缀表达式是将运算符放在两个操作数之前。后缀...
  • 表达式一般分为前缀表达式,中缀表达式和后缀表达式。其中我们最为熟悉的是中缀表达式,也就是书本上最常用的表示形式。中缀表达式是将运算符放在两个操作数的中间。前缀表达式是将运算符放在两个操作数之前。后缀...
  • 20世纪50年代,波兰逻辑学家卢卡西维奇(Lukasiewicz)发明了一种不需要括号的表达式,我们把波兰式称为前缀表达式,把逆波兰式称为后缀表达式。接下来就介绍如何将中缀表达式转化为前缀、后缀表达式,这里介绍的方法...
  • 常见的表达式为中缀表达式...前缀表达式: 把运算符号移动到对应的括号前面 则变成了:-(+(a*(bc))+(de)) 去掉括号后:-+a*bc+de 后缀表达式: 把运算符号移动到对应的括号前面 则变成:((a(bc)∗)+(de)+)−((a(...
  • 题目:将中序表达式转换为前缀表达式和后缀表达式,例如: (a+b)c(d-e/f) 转换成前缀表达式是:*-/fed*c+ba ,转换为后缀表达式是:ab+c*def/- * 输入:(a+b)c(d-e/f) 输出:前缀:*-/fed*c+ba,后缀表达式是...
  • 1、如何将中缀表达式转化成后缀表达式呢?(计算机中用的就是后缀表达式) 利用两个栈S1,S2:其中S1存放操作符,S2存放操作数 从左往右遍历中缀表达式,如果遇到数字,则放入S2中,如果遇到操作符,则放入S1中。...
  •  ①、如何将中缀表达式转换为前缀表达式?  ②、计算机如何实现前缀表达式的运算?    前面我们介绍了三种数据结构,第一种数组主要用作数据存储,但是后面的两种栈和队列我们说主要作为程序...
  • 文章目录前言各种表达式$Code$怎么转换 前言 数学杂谈这个东西。。。我好像已经很久没有更新了吧。。。QwQ 当然,今天作为某道题的基础,这当然是必不可少的了。...一般来说,计算机用到的都是前缀表达式和后缀...
  • 什么是 前缀表达式什么是中缀表达式什么是后缀表达式为啥需要前缀表达式,后缀表达式 ?如何将中缀表达式转化为 后缀表达式呢?后缀表达式如何计算的 ?[150. 逆波兰表达式求值]...
  • 如何将中缀表达式转换成后缀表达式 按运算符的优先级对所有的运算符和它的运算数加括号。 把运算符移到对应的括号后。 去掉括号。 前缀表达式其实将运算符提到括号的前面,其他都一样。 ...
  • 表达式转化(中缀,后缀,前缀) 1、为什么要把中缀表达式转化为后缀,前缀?...2、中缀如何计算后缀,前缀表达式? 计算后缀:从左到右遍历后缀表达式,遇到操作数,放进栈,遇到操作符,栈顶两个数出栈,进...
  • 前缀表达式的时候在移括号的时候将运算符移到括号的左边再去括号就可以了 计算机计算前缀和后缀表达式比较容易(用栈讲,读后缀表达式,遇到数字,将其压栈,遇到运算符时,栈顶出栈放到运算符的右边,在出栈一个...
  • 2、计算机如何计算后缀,前缀表达式? 计算后缀:从左到右遍历后缀表达式,遇到操作数,放进栈,遇到操作符,栈顶两个数出栈,进行运算,运算结果放进栈,直到读完后缀表达式。 计算前缀:从左到右遍历前缀表达式...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 210
精华内容 84
关键字:

如何前缀表达式