列表

详情

MMT10. 中缀表达式转后缀表达式

描述

将中缀表达式转为后缀表达式，输入 a+b*c/d-a+f/b 输出 abc*d/+a-fb/+
要求：语言不限；输入输出均为单个字符串；操作数用单个小写字母表示，操作符只需支持 +-*/，按照四则运算顺序确定优先级，不包含括号

输入描述

一个字符串为合法的中缀表达式
字符串长度不超过200000

输出描述

对应的后缀表达式

示例1

输入: 

a+b*c/d-a+f/b

输出: 

abc*d/+a-fb/+

原站题解

C 解法, 执行用时: 4ms, 内存消耗: 772KB, 提交时间: 2020-05-13 

#include <stdlib.h>
#include <string.h>
  
//预定义运算符的优先级表,数值越大优先级越高
unsigned char priorityTable[128] = {};
  
void bilateral2backward(char * bilateral){
    priorityTable['+'] = 5;
    priorityTable['-'] = 5;
    priorityTable['*'] = 6;
    priorityTable['/'] = 6;
    int expressionEndianIndex=0;
    while(bilateral[expressionEndianIndex++] != '\0');
    char * numberStack = (char *)calloc(expressionEndianIndex,1);
    char * operatorStack = (char *)calloc(expressionEndianIndex,1);
    int m=0,n=0;
    for(int i=0;i<expressionEndianIndex;i++){
        if(bilateral[i] >= 'a' && bilateral[i] <= 'z'){
            numberStack[m++] = bilateral[i];
        }else if(priorityTable[bilateral[i]] != 0){
            if(priorityTable[operatorStack[n]] < priorityTable[bilateral[i]]){
                operatorStack[++n] = bilateral[i];
            }else{
                while(priorityTable[operatorStack[n]] >= priorityTable[bilateral[i]]){
                    numberStack[m++] = operatorStack[n--];
                }
                operatorStack[++n] = bilateral[i];
            }
        }else{
            continue;
        }
    }
    while(n > 0)
        numberStack[m++] = operatorStack[n--];
      
    memcpy(bilateral,numberStack,m);
    free(numberStack);
    free(operatorStack);
}
  
int main(void)
{
    char inputStr[200001];
    scanf("%s",inputStr);
    bilateral2backward(inputStr);
    printf("%s\n",inputStr);
    return 0;
}

C 解法, 执行用时: 4ms, 内存消耗: 796KB, 提交时间: 2020-04-10 

#include <stdlib.h>
#include <string.h>

//预定义运算符的优先级表,数值越大优先级越高
unsigned char priorityTable[128] = {};

void bilateral2backward(char * bilateral){
    priorityTable['+'] = 5;
    priorityTable['-'] = 5;
    priorityTable['*'] = 6;
    priorityTable['/'] = 6;
    int expressionEndianIndex=0;
    while(bilateral[expressionEndianIndex++] != '\0');
    char * numberStack = (char *)calloc(expressionEndianIndex,1);
    char * operatorStack = (char *)calloc(expressionEndianIndex,1);
    int m=0,n=0;
    for(int i=0;i<expressionEndianIndex;i++){
        if(bilateral[i] >= 'a' && bilateral[i] <= 'z'){
            numberStack[m++] = bilateral[i];
        }else if(priorityTable[bilateral[i]] != 0){
            if(priorityTable[operatorStack[n]] < priorityTable[bilateral[i]]){
                operatorStack[++n] = bilateral[i];
            }else{
                while(priorityTable[operatorStack[n]] >= priorityTable[bilateral[i]]){
                    numberStack[m++] = operatorStack[n--];
                }
                operatorStack[++n] = bilateral[i];
            }
        }else{
            continue;
        }
    }
    while(n > 0)
        numberStack[m++] = operatorStack[n--];
    
    memcpy(bilateral,numberStack,m);
    free(numberStack);
    free(operatorStack);
}

int main(void)
{
    char inputStr[200001];
    scanf("%s",inputStr);
    bilateral2backward(inputStr);
    printf("%s\n",inputStr);
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 888KB, 提交时间: 2020-10-31 

#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
char str[200000];
char str_1[200000];
stack<char> s;
bool f(char A,char B)
{
    if(A=='+'||A=='-')
    {
        return false;
    }
    else
    {
        if(B=='+'||B=='-')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        int len=strlen(str);
        int idx=0;
        for(int i=0;i<len;i++)
        {
            if(str[i]>='a'&&str[i]<='z')
            {
                str_1[idx++]=str[i];
                //printf()
            }
            else
            {
                if(s.empty()==true)
                {
                    s.push(str[i]);
                }
                else
                {
                    bool flag=f(str[i],s.top());
                    if(flag)
                    {
                        s.push(str[i]);
                    }
                    else
                    {
                        while(flag==false)
                        {
                            str_1[idx++]=s.top();
                            //printf("i:%d %c\n",i,s.top());
                            s.pop();
                            if(s.empty())
                            {
                                break;
                            }
                            flag=f(str[i],s.top());
                        }
                        s.push(str[i]);
                    }
                }
            }
        }
        //printf("11\n");
        while(s.empty()==false)
        {
            str_1[idx++]=s.top();
            s.pop();
        }
        str_1[idx]=0;
        printf("%s\n",str_1);
    }
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 892KB, 提交时间: 2020-11-01 

#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
char str[200000];
char str_1[200000];
stack<char> s;
bool f(char A,char B)
{
    if(A=='+'||A=='-')
    {
        return false;
    }
    else
    {
        if(B=='+'||B=='-')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        int len=strlen(str);
        int idx=0;
        for(int i=0;i<len;i++)
        {
            if(str[i]>='a'&&str[i]<='z')
            {
                str_1[idx++]=str[i];
                //printf()
            }
            else
            {
                if(s.empty()==true)
                {
                    s.push(str[i]);
                }
                else
                {
                    bool flag=f(str[i],s.top());
                    if(flag)
                    {
                        s.push(str[i]);
                    }
                    else
                    {
                        while(flag==false)
                        {
                            str_1[idx++]=s.top();
                            //printf("i:%d %c\n",i,s.top());
                            s.pop();
                            if(s.empty())
                            {
                                break;
                            }
                            flag=f(str[i],s.top());
                        }
                        s.push(str[i]);
                    }
                }
            }
        }
        //printf("11\n");
        while(s.empty()==false)
        {
            str_1[idx++]=s.top();
            s.pop();
        }
        str_1[idx]=0;
        printf("%s\n",str_1);
    }
    return 0;
}

C 解法, 执行用时: 4ms, 内存消耗: 992KB, 提交时间: 2020-05-19 

#include <stdlib.h>
#include <string.h>
   
//预定义运算符的优先级表,数值越大优先级越高
unsigned char priorityTable[128] = {};
   
void bilateral2backward(char * bilateral){
    priorityTable['+'] = 5;
    priorityTable['-'] = 5;
    priorityTable['*'] = 6;
    priorityTable['/'] = 6;
    int expressionEndianIndex=0;
    while(bilateral[expressionEndianIndex++] != '\0');
    char * numberStack = (char *)calloc(expressionEndianIndex,1);
    char * operatorStack = (char *)calloc(expressionEndianIndex,1);
    int m=0,n=0;
    for(int i=0;i<expressionEndianIndex;i++){
        if(bilateral[i] >= 'a' && bilateral[i] <= 'z'){
            numberStack[m++] = bilateral[i];
        }else if(priorityTable[bilateral[i]] != 0){
            if(priorityTable[operatorStack[n]] < priorityTable[bilateral[i]]){
                operatorStack[++n] = bilateral[i];
            }else{
                while(priorityTable[operatorStack[n]] >= priorityTable[bilateral[i]]){
                    numberStack[m++] = operatorStack[n--];
                }
                operatorStack[++n] = bilateral[i];
            }
        }else{
            continue;
        }
    }
    while(n > 0)
        numberStack[m++] = operatorStack[n--];
       
    memcpy(bilateral,numberStack,m);
    free(numberStack);
    free(operatorStack);
}
   
int main(void)
{
    char inputStr[200001];
    scanf("%s",inputStr);
    bilateral2backward(inputStr);
    printf("%s\n",inputStr);
    return 0;
}

上一题

© 2024 nowcoder.com