0

我真的被困在我们任务的特殊前缀到后缀操作的转换中，让我类似地描述一下这个任务：

我们有这样的操作用作前缀中的操作，这是我正在检查它们的方法：

bool isOperator(string c)
{
    if (c == "log" || c == "exp" || c == "sum" || c == "div" || c == "abs" || c == "sqrt" || c == "sub" || c == "product" || c == "max" || c== "min" || c == "mod" )     // you may add operator here
        return true;
    return false;
}

无论如何，示例前缀指令可以有括号来使操作优先，这就是我所坚持的。我知道，我需要实现这样的递归，但我找不到方法。

div ( sqrt 5 ) 3

输出应该是

5 sqrt 3 div

另一个例子 ：

div ( sum ( exp 2 3 ) ( sqrt 5 ) ) 3

输出

2 3 exp 5 sqrt sum 3 div

在假定条件下，每个操作、括号或数字都应该在元素之间留有空格。

我的堆栈实现

堆栈.h

#include<iostream>
using namespace std;

struct node {
    string op ;
    node *next;
};

struct Stack {
    node * head;
    void create();
    void close();
    void push (node *);
    node* pop();
    node* top();
    bool isEmpty();

};

堆栈.cpp

#define _CRT_SECURE_NO_WARNINGS
#include "stack.h"
#include <iostream>
#include <stdlib.h>

void Stack::create() {
    head = NULL;
}

void Stack::close() {
    node *p;
    while (head) {
        p = head;
        head = head->next;
        //delete [] p->data;
        delete p;
    }
}

void Stack::push(node *newdata) {
    node *newnode = new node;
    newnode = newdata;
    newnode->op = newdata->op;
    newnode->next = head;
    head = newnode;
}

node *Stack::pop() {
    if (isEmpty())
        return NULL;
    node *topnode = head;
    head = head->next;
    //delete topnode;
    return topnode;
}

node *Stack::top() {
    if (isEmpty())
        return NULL;
    node *topnode = head;
    //delete topnode;
    return topnode;
}
bool Stack::isEmpty() {
    return (head == NULL);
}

正如@PaulMcKenzie 提到的，我在下面尝试了一个实现， sub_array 字符串数组包含不带空格的单词列表。

bool isLeftParanthesis(string c)
{
    if (c == "(" )   // you may add operator here
        return true;
    return false;
}
bool isRightParanthesis(string c)
{
    if (c == ")")    // you may add operator here
        return true;
    return false;
}
int main()
{
string prefix;
getline(cin, prefix);
istringstream iss(prefix);
istringstream iss2(prefix);
int count1 = 0, count2 = 0;
string postfix = "";
Stack *st = new Stack;
string t1, t2;

string sub;
string *sub_array;
while (iss >> sub) {
    count1++;
}
sub_array = new string[count1];
while (iss2 >> sub) {
    sub_array[count2] = sub;
    count2++;
}
int l = count1;

int right_p_count = 0;
for (int i = 0; i < count1; i++)
{
    if (isRightParanthesis(sub_array[i]))
    {
        right_p_count++;
    }
}
string *postfixes = new string[right_p_count];
int index_right_p = 0;
for (int i = 0; i < count1; i++) {
    while (!isRightParanthesis(sub_array[i]))
    {
        node *n = new node;
        n->op = sub_array[i];
        st->push(n);
        i++;
        if (i == count1)
        {
            break;
        }
    }
    if( i != count1){
    if (isRightParanthesis(sub_array[i])) {
        postfix = "";
        while (!isLeftParanthesis(st->top()->op))
        {
            string t = st->pop();
            if (!isOperator(t) && !isLeftParanthesis(t) && !isRightParanthesis(t)) {
                postfix = t + " " + postfix;
            }
            else if (isOperator(t)) {
                postfix = postfix + " " + t;
            }
        }
        st->pop();
        postfixes[index_right_p] = postfix;
        index_right_p++;
    }
    }
    postfix = "";
    while ( !st->isEmpty() && index_right_p == right_p_count && i == count1)
    {
        string t = st->pop();
        if (!isOperator(t) && !isLeftParanthesis(t) && !isRightParanthesis(t)) {
            postfix = t+" "+postfix;
        }
        else if (isOperator(t)) {
            postfix = postfix+""+t;
        }
        else {
            break;
        }
    }
}

string result = "";
for (int i = 0; i < right_p_count; i++)
{
    result = result + "" + postfixes[i];
}
result = result + " " + postfix;
cout << result << endl;
}

变量后缀是指输出后缀，但是我的输出对于一些操作没有错，比如：

div ( sqrt 5 ) 3

当我看到一个括号时，我正在检查它是左还是右，使用右一个作为触发器。

abs ( product -2 -4 -8 )

预期输出为：

-2 -4 -8 product abs

更新：我自己解决了堆栈问题，但发现算法错误地计算了一些表达式......

示例表达式：

3 2 3 exp sum

预期输出：

sum 3 ( exp 2 3 )

我的输出：

2 3 exp 3 sum

我的算法使用右括号作为触发器计算错误，我不知道如何实现这个控件，有什么建议吗？

4

0 回答 0