论坛 › C\C++交流 › C语言程序

蓝黑色眼睛 发表于 2017-12-21 15:05:37

C语言程序

【描述】编写一个计算中缀表达式计算的程序。运算符包括+、-、*、/、(、)，操作数可以是多位数和浮点数。要求程序从输入文件input.txt读取表达式，并将计算结果写入输出文件output.txt，计算结果保留小数点后2位，四舍五入。输入表达式有错误时，输出“错误”。

要求能够处理多位整数/浮点数，能否发现表达式的语法错误。

【文件格式】
输入文件intput.txt
第1行是一个整数n表示表达式个数
接下来n行，每行一个表达式，表达式的符号之间不含空格。
输出文件output.txt
输出文件共n行，每行对应输入表达式的计算结果。
【数据范围】60%的表达式中操作数为个位整数，每个表达式的最大长度为100个字符。
【输入样例】input.txt
10
2+3)
2-3
2*3
4/2
2+3*2
3*2-1
4/2*3
12*3+3
15/3-3
10.5-5+3
【输出样例】output.txt
错误
-1.00
6.00
2.00
8.00
5.00
6.00
39.00
2.00
8.50
【提交】
提交(1)源程序 (2)报告（核心是给出所实现的算法的自然语言的描述）

BngThea 发表于 2017-12-21 15:08:58

所以，你的思路呢？

newu 发表于 2017-12-21 19:52:56

你不会是到这里来要作业答案来了吧？

kai759630 发表于 2017-12-21 20:53:25

看了问题，我的初步思路是：首先分割文件中每一行，然后将每一行数据按照运算符进行分割，如果有左括号，那就找到右括号进行分割，接下来是翻译，将表达式中想要表达的意思转化成计算机能看懂的意思。（附加：你的运算式必须是正确且无歧义的，否则简单的程序是无法解决这个问题的）
有两个难点：
1 分割：如何将文件读取的字符按照正确的格式转化为相应的数字、运算符、括号，进行分割时顺序必须不能改变否则会将表达式翻译错误。
2 定义：或者说翻译，如何像编译器一样将转化后表达式的意思翻译成数学运算，也就是说"1 + 1"，计算机怎么知道这个"+"是数学运算而不是一个字符？懂编译原理的人应该能解决这个问题。
可能有理解上的问题，还望大神指正(*^_^*)

人造人 发表于 2017-12-22 00:21:03

我用C++写了一个，仅供参考
注：程序没有错误处理，增加错误处理会让代码变得更长，如果没有必要，就不加了

main.cpp
#include <iostream>
#include <string>
#include "expression.h"

int main(void)
{
        //Expression e("((12 + 1) * 3 - 1) - (12 - 1) * (3 + 3)");
        Expression e;

        std::string expression;
        while(std::getline(std::cin, expression))
        {
                e.SetExpression(expression.c_str());
                e.PrintInfixExpression();
                e.PrintPostfixExpression();
                std::cout << e.Calculate() << std::endl;
        }

        return 0;
}


expression.cpp
#include "expression.h"
#include <iostream>
#include <stack>

Expression::Expression()
{

}

Expression::Expression(const char *expression)
{
        SetExpression(expression);
}

void Expression::SetExpression(const char *expression)
{
        infixExpression.clear();
        postfixExpression.clear();

        ParseString(infixExpression, expression);
        InfixExpressionToPostfixExpression(postfixExpression, infixExpression);
}

void Expression::ParseString(std::vector<Element> &expr, const char *expression)
{
        Element element;
        const char *index = expression;

        while(index = GetElement(element, index))
                expr.push_back(element);
}

const char *Expression::GetElement(Element &element, const char *str)
{
        if(*str == '\0')
                return NULL;

        if(('0' <= *str) && (*str <= '9'))
        {
                //数字
                element.elementType = Element::NUMBER;
                element.data.num = element.data.num = 0;

                std::vector<char> vchar;
                while(1)
                {
                        if(!(('0' <= *str) && (*str <= '9')))
                                if(*str != '.')
                                        break;

                        vchar.push_back(*str);
                        str++;
                }

                bool is_integer = true;
                double scale = 10;
                std::vector<char>::iterator iter;
                for(iter = vchar.begin(); iter != vchar.end(); iter++)
                {
                        if(is_integer)
                        {
                                if(*iter == '.')
                                {
                                        is_integer = false;
                                        continue;
                                }

                                element.data.num = element.data.num * 10 + (*iter - '0');
                        }
                        else
                        {
                                element.data.num += (*iter - '0') / scale;
                                scale *= 10;
                        }
                }
        }
        else
        {
                //符号
               
                if(*str == ' ')
                {
                        str = GetElement(element, ++str);
                        return str;
                }
               
                element.elementType = Element::SYMBOL;
                element.data.ch   = *str;
               
                str++;
        }

        return str;
}

void Expression::PrintInfixExpression(void)
{
        PrintExpression(infixExpression);
}

void Expression::PrintPostfixExpression(void)
{
        PrintExpression(postfixExpression);
}

void Expression::PrintExpression(std::vector<Element> &expression)
{
        for(std::vector<Element>::iterator iter = expression.begin(); iter != expression.end(); iter++)
        {
                Element element = *iter;
                if(element.elementType == Element::SYMBOL)
                {
                        std::cout << element.data.ch;
                }
                else
                {
                        std::cout << element.data.num;
                }

                std::cout << ' ';
        }

        std::cout << std::endl;
}

bool Expression::InfixExpressionToPostfixExpression(std::vector<Element> &postfixExpression, const std::vector<Element> &infixExpression)
{
        std::stack<Element> stack;
        for(std::vector<Element>::const_iterator iter = infixExpression.begin(); iter != infixExpression.end(); iter++)
        {
                Element element = *iter;
                if(element.elementType == Element::NUMBER)
                {
                        postfixExpression.push_back(element);
                }
                else
                {
                        if(stack.empty())
                        {
                                stack.push(element);
                                continue;
                        }

                        if(element.data.ch == '(')
                        {
                                stack.push(element);
                                continue;
                        }

                        if(element.data.ch == ')')
                        {
                                PopStack(postfixExpression, stack);
                                continue;
                        }

                        if(GetPriority(element.data.ch) >= GetPriority(stack.top().data.ch))
                        {
                                stack.push(element);
                        }
                        else
                        {
                                PopStack(postfixExpression, stack);
                                stack.push(element);
                        }
                }
        }

        while(!stack.empty())
        {
                Element elementTmp = stack.top();
                stack.pop();
                postfixExpression.push_back(elementTmp);
        }

        return true;
}

inline unsigned int Expression::GetPriority(char ch)
{
        switch(ch)
        {
        case '(':
        case ')':
                return 0;
        case '+':
        case '-':
                return 1;
        case '*':
        case '/':
                return 2;
        default:
                return -1;
        }
}

void Expression::PopStack(std::vector<Element> &postfixExpression, std::stack<Element> &stack)
{
        while(!stack.empty())
        {
                Element element = stack.top();
                stack.pop();

                if(element.data.ch != '(')
                        postfixExpression.push_back(element);
                else
                        break;
        }
}

double Expression::Calculate(void)
{
        std::stack<Element> stack;
        for(std::vector<Element>::const_iterator iter = postfixExpression.begin(); iter != postfixExpression.end(); iter++)
        {
                Element element = *iter;
                if(element.elementType == Element::NUMBER)
                {
                        stack.push(element);
                }
                else
                {
                        double num1, num2;
                        Element elementTmp;

                        elementTmp = stack.top();
                        stack.pop();
                        num1 = elementTmp.data.num;

                        elementTmp = stack.top();
                        stack.pop();
                        num2 = elementTmp.data.num;

                        switch(element.data.ch)
                        {
                        case '+':
                                elementTmp.data.num = num2 + num1;
                                stack.push(elementTmp);
                                break;
                        case '-':
                                elementTmp.data.num = num2 - num1;
                                stack.push(elementTmp);
                                break;
                        case '*':
                                elementTmp.data.num = num2 * num1;
                                stack.push(elementTmp);
                                break;
                        case '/':
                                if(num1 == 0)
                                        throw "除数为0";

                                elementTmp.data.num = num2 / num1;
                                stack.push(elementTmp);
                                break;
                        }
                }
        }

        Element elementTmp = stack.top();
        stack.pop();

        return elementTmp.data.num;
}


expression.h
#ifndef _EXPRESSION_H_
#define _EXPRESSION_H_

#include <vector>
#include <stack>

class Expression
{
public:
        Expression();
        Expression(const char * expression);
        void SetExpression(const char *expression);
        double Calculate(void);
        void PrintInfixExpression(void);
        void PrintPostfixExpression(void);

private:
        typedef struct
        {
                enum{ NUMBER, SYMBOL }        elementType;
                union { char ch; double num; }        data;
        } Element;

        std::vector<Element> infixExpression;
        std::vector<Element> postfixExpression;

        void ParseString(std::vector<Element>& expr, const char *expression);
        const char *GetElement(Element &element, const char *str);
       
        inline unsigned int GetPriority(char ch);
        void PopStack(std::vector<Element> &postfixExpression, std::stack<Element> &stack);
        bool InfixExpressionToPostfixExpression(std::vector<Element> &postfixExpression, const std::vector<Element> &infixExpression);
        void PrintExpression(std::vector<Element> &expression);
};

#endif

蓝黑色眼睛 发表于 2017-12-22 18:34:23

人造人 发表于 2017-12-22 00:21
我用C++写了一个，仅供参考
注：程序没有错误处理，增加错误处理会让代码变得更长，如果没有必要，就不加 ...

有读文件和写文件的操作吗

人造人 发表于 2017-12-22 18:56:16

蓝黑色眼睛 发表于 2017-12-22 18:34
有读文件和写文件的操作吗

没有，想要就自己加

查看完整版本: C语言程序