炫意html5
最早CSS3和HTML5移动技术网站之一

数据结构c++表达式计算

想让大家帮我看看我的代码哪里错了,谢谢了
题目:
表达式计算
Time Limit: 1000 MS Memory Limit: 1000 KB

Description

输入一串表达式,计算其结果。表达式包括数字’0’~’9’、’+’、’-‘、’*’、’/’、'(‘、’)’,并以符号’#’结尾。
在计算中,除法以向下取整计算。
保证表达式合法,且结果不超过long long范围。

Input

输入的第一行是一个int型整数T,表示一个有T组数据。
接下来T行,每行一个一个表达式。

Output

输出T行,每行一个整数,表示求得的结果。

Sample Input

2
1-2#
3*(1+2)#

Sample Output

-1
9

我的代码如下(其中中缀转后缀的地方是完全正确的,后缀计算那里有些问题,提交后显示runtime error):

#include <iostream>
#include <string>
#include <stack>
using namespace std;
//操作符的栈内、外优先级
int isp(char x)//栈内
{
if (x == '*' || x == '/') return 5;
if (x == '+' || x == '-') return 3;
if (x == '(') return 1;
else return -1;
}
int icp(char x)//栈外
{
if (x == '*' || x == '/') return 4;
if (x == '+' || x == '-') return 2;
if (x == '(') return 6;
else return -1;
}
int main()
{
string infix, postfix;
stack<char> operators;
int T;
cin >> T;
char ch;
for (int q = 0; q < T; ++q)
{
cin >> infix;
for (int i = 0; infix[i] != '#'; i++)
{
ch = infix[i];
if (ch >= '0' && ch <= '9')
{//是操作数,输出
postfix.push_back(ch);
}
else if (operators.empty())
{//若是空的,让该操作符进栈
operators.push(ch);
}
else if (ch == ')')
{
while (operators.top() != '(' && !operators.empty())
{
postfix.push_back(operators.top());
operators.pop();
}
operators.pop();
}
else if (ch == '(')
{
operators.push(ch);
}
else if (ch == '+' || ch == '-'
|| ch == '*' || ch == '/')
{//是加减乘除
while (isp(operators.top()) >= icp(ch))
{
postfix.push_back(operators.top());
operators.pop();
if (operators.empty())
{
break;
}
}
operators.push(ch);
}
}
while (!operators.empty())
{
postfix.push_back(operators.top());
operators.pop();
}
//储存数字
stack<long long int> re;
//开始进行计算
char op;
for (int y = 0; y < postfix.size(); ++y)
{
op = postfix[y];
if (op >= '0' && op <= '9')
{
int l = op - '0';
re.push(l);
}
else
{
//出栈顶两个数字
long long int a = re.top();
re.pop();
long long int b = re.top();
re.pop();
if (op == '+')
{//加
re.push(a + b);
}
else if (op == '-')
{//减
re.push(b - a);
}
else if (op == '*')
{//乘
re.push(a * b);
}
else if (op == '/')
{//除
re.push(b / a);
}
}
}
long long int result = re.top();
cout << result << endl;
infix.clear();
postfix.clear();
}
return 0;
}

回答

今天又看了看这道题,解决了,原因是计算的时候,我原以为都是一位的数(即没有1+87这种的),现支持了多位数的运算。我的思路是在后缀表达式的两个数字之间用“.”来分隔开。
代码如下:

#include <iostream>
#include <string>
#include <stack>

using namespace std;

//操作符的栈内、外优先级
int isp(char x)//栈内
{
    if (x == '*' || x == '/') return 5;
    if (x == '+' || x == '-') return 3;
    if (x == '(') return 1;
    else return -1;
}
int icp(char x)//栈外
{
    if (x == '*' || x == '/') return 4;
    if (x == '+' || x == '-') return 2;
    if (x == '(') return 6;
    else return -1;
}

int main()
{
    //postfix的存储中,一个数字结束 用.来表示
    string infix, postfix;
    stack<char> operators;
    int T;
    cin >> T;
    char ch;
    for (int q = 0; q < T; ++q)
    {
        cin >> infix;
        for (int i = 0; infix[i] != '#'; i++)
        {
            ch = infix[i];
            if (ch >= '0' && ch <= '9')
            {//是操作数,输出
                postfix.push_back(ch);
            }
            else if (operators.empty())
            {//若是空的,让该操作符进栈
                operators.push(ch);
                postfix.push_back('.');
            }
            else if (ch == ')')
            {
                while (operators.top() != '(' && !operators.empty())
                {
                    postfix.push_back('.');
                    postfix.push_back(operators.top());
                    operators.pop();
                }
                operators.pop();
            }
            else if (ch == '(')
            {
                postfix.push_back('.');
                operators.push(ch);
            }
            else if (ch == '+' || ch == '-'
                || ch == '*' || ch == '/')
            {//是加减乘除
                postfix.push_back('.');
                while (isp(operators.top()) >= icp(ch))
                {
                    postfix.push_back(operators.top());
                    operators.pop();
                    if (operators.empty())
                    {
                        break;
                    }
                }
                operators.push(ch);
            }
        }
        while (!operators.empty())
        {
            postfix.push_back(operators.top());
            operators.pop();
        }
        //储存数字
        stack<long long int> re;
        //re顶的数字与正在读的数字是否属于一个数字
        bool iN = true;
        //开始进行计算
        char op;
        for (int y = 0; y < postfix.size(); ++y)
        {
            op = postfix[y];
            if ((op >= '0' && op <= '9'))
            {
                int l = op - '0';
                if (iN == true)
                {//是新的数字,直接入栈
                    re.push(l);
                    iN = false;
                }
                else
                {//不是新的数字
                    l += re.top() * 10;
                    re.pop();
                    re.push(l);
                }
            }
            else if (op == '.')
            {//前一个数字结束
                iN = true;
            }
            else
            {
                //出栈顶两个数字
                long long int a = re.top();
                re.pop();
                long long int b = re.top();
                re.pop();
                if (op == '+')
                {//加
                    re.push(a + b);
                    iN = true;
                }
                else if (op == '-')
                {//减
                    re.push(b - a);
                    iN = true;
                }
                else if (op == '*')
                {//乘
                    re.push(a * b);
                    iN = true;
                }
                else if (op == '/')
                {//除
                    re.push(b / a);
                    iN = true;
                }
            }
        }
        long long int result = re.top();
        cout << result << endl;
        infix.clear();
        postfix.clear();
    }
    return 0;
}

炫意HTML5 » 数据结构c++表达式计算

Java基础教程Android基础教程